01背包问题

题目要求

  • 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

示例 1:
背包最大重量为4。

物品为：

物品 重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

问背包能背的物品最大价值是多少？

动态规划

动规五部曲

  1. 确定dp数组（dp table）以及下标的含义
    dp[i][j]代表编号为[0,i]的物品中，背包最大重量为j时的最大价值

  2. 确定递推公式
    对于指定物品i，有两种情况：

  • 不放入物品i，那么最大价值就是dp[i-1][j]
  • 放入物品i，那么最大价值就是dp[i-1][j-weight[i]] + value[i]
    因此递推公式为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

  1. dp数组如何初始化

    由递推公式可知，dp[i][j]的值依赖于dp[i-1][j]和dp[i-1][j-weight[i]]，因此需要初始化dp[0][j]和dp[i][0]
    dp[0][j] = 0（装不下物品0时最大价值为0，装得下时最大价值为物品0的价值）
    dp[i][0] = 0（背包最大重量为0时，最大价值为0）
    对于其他位置的初始化，因为后面做的是覆盖操作，所以初始化成什么都不影响结果

  2. 确定遍历顺序
    因为dp[i][j]依赖于dp[i-1][j]和dp[i-1][j-weight[i]]，因此需要先遍历i还是先遍历j都可以

  3. 举例推导dp数组

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
40
41
42
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int bagweight = scanner.nextInt();

        // 初始化物品重量和价值数组
        int[] weight = new int[n];
        int[] value = new int[n];

        for (int i = 0; i < n; ++i) {
            weight[i] = scanner.nextInt();
        }
        for (int j = 0; j < n; ++j) {
            value[j] = scanner.nextInt();
        }

        // 初始化dp数组
        int[][] dp = new int[n][bagweight + 1];

        // 装得下物品0时的最大价值
        for (int j = weight[0]; j <= bagweight; j++) {
            dp[0][j] = value[0];
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= bagweight; j++) {
                // 如果背包容量小于当前物品重量，则不能放入该物品
                if (j < weight[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 如果背包容量大于等于当前物品重量，则可以选择放入或不放入该物品
                    // 不放入物品i：dp[i - 1][j]
                    // 放入物品i：dp[i - 1][j - weight[i]] + value[i]
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                }
            }
        }
      
        System.out.println(dp[n - 1][bagweight]);
    }
}