1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
    public static void main(String[] args) {
        // 重量
        int[] weight = new int[]{4, 6, 2, 2, 5, 1};
        // 价值
        int[] value = new int[]{8, 10, 6, 3, 7, 2};
        // 计算最大价值
        int sum = method(12, value.length, weight, value);
        System.out.println(sum);
    }

    /**
     * @param itemType         背包容量
     * @param backpackCapacity 物品种类
     * @param weight           物品重量
     * @param value            物品价值
     */
    public static int method(int itemType, int backpackCapacity, int[] weight, int[] value) {
        int[][] dp = new int[backpackCapacity + 1][itemType + 1];
        for (int i = 1; i < backpackCapacity + 1; i++) {
            for (int j = 1; j < itemType + 1; j++) {
                // weight[i - 1] 中 i - 1 是因为 i 从 1 开始,所以 i - 1 表示的是第一个物品
                if (weight[i - 1] > j) {
                    // 如果物品比当前背包还重,那么没法添加新物品
                    // 那么则选中上一个容量装的最大价值作为当前的最大价值
                    dp[i][j] = dp[i - 1][j];
                }
                else {
                    // 如果当前背包能够装下该物品,那么则在上一个容量装的最大价值和
                    // 装进这个物品的最大价值之间做一个比较,取最大值
                    // dp[i - 1][j] 表示的就是上一个容量装的最大价值
                    // dp[i - 1][j - weight[i - 1]] + value[i - 1] 要拆成两部分来看
                    // 先看 dp[i - 1][j - weight[i - 1]],它是上一个物品在能装下新物品时的最大价值
                    // value[i - 1] 是当前物品的最大价值,合起来便是将当前物品装入背包的最大价值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                }
            }
        }
        return dp[backpackCapacity][itemType];
    }