题解 | #01背包#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    public int knapsack (int V, int n, int[][] vw) {
        // write code here
        int[] weight=new int[n];
        int[] value=new int[n];

        for(int i=0;i<n;i++){
            weight[i]=vw[i][0];
            value[i]=vw[i][1];
        }

        return process(weight,value,n,V);
    }

    int[][] memo ;
    int[] weight;
    int[] value;
    int n;

    public int process(int[] weight, int[] value, int n, int bagWeight) {
        memo= new int[n][bagWeight + 1];
        for(int i=0;i<n;i++){
            Arrays.fill(memo[i],-1);
        }

        this.weight=weight;
        this.value=value;
        this.n=n;
        return process(0,bagWeight);
    }

// 来到物品index这里，装还是不装，bagAvl表示背包剩余体积,gv表示已经获取的价值
    public int process(int index,
                       int bagAvl) {
        if (bagAvl == 0 || index == n) {
            // 背包已经装满 或者 已经对所有物品都进行了选择
            return 0;
        }
        if (memo[index][bagAvl] != -1) {
            return memo[index][bagAvl];
        }

        // 不装
        int p1 = process(index + 1,bagAvl);
        // 装
        int p2 = 0;
        if (bagAvl >= weight[index]) {
            p2 = process(index + 1,bagAvl-weight[index])+value[index];
        }

        memo[index][bagAvl] = Math.max(p1, p2);
        return memo[index][bagAvl];
        // return  Math.max(p1, p2);
    }
}