day41【代码随想录】动态规划之01背包问题_动态规划01背包问题代码

---

前言 01背包

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

来源：链接: linkand链接: link

---

一、二维dp数组01背包

1.1 确定dp数组以及下标的含义

dp[i][j]表示从下标为 0—i 的物品中，放进容量为j的背包，价值总和最大是多少。

1.2 确定递推公式

可以有两个方向推出dp[i][j]

• 不放物品i：也就是说当前物品的重量weight[i]> 背包容量j 时，物品无法放入背包，所以背包中的价值依然和之前相同 dp[i][j] = dp[i-1][j];
• 放物品i：也就是说，当前的背包容量j是可以满足当前物品的重量，没有放入物品i之前的背包最大价值为 dp[i-1][j-weight[i]]；放入物品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.3 初始化

如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

for (int j = 0 ; j < weight[0]; j++) {
    dp[0][j] = 0;
}
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}
1
2
3
4
5
6

其实从递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出dp[i][j] 是由左上方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖。

1.4 遍历顺序

有两个遍历的维度：物品与背包重量

先遍历 物品还是先遍历背包重量呢？

先遍历物品，再遍历背包的过程如图所示：

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.length; i++) { // 遍历物品
    for(int j = 1; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; 
        else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}
1
2
3
4
5
6
7

先遍历背包，再遍历物品：

// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.length; i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}
1
2
3
4
5
6
7

都可以，因为正如上边所说 数值推导是由左上方来的

虽然两个for循环遍历的次序不同，但是dp[i][j]所需要的数据就是左上角，不会影响dp[i][j]公式的推导！

1.5推导dp数组

1.6 完整代码

public class BagProblem {
    public static void main(String[] args) {
        int[] weight = {1,3,4};
        int[] value = {15,20,30};
        int bagSize = 4;
        testWeightBagProblem(weight,value,bagSize);
    }

    /**
     * 动态规划获得结果
     * @param weight  物品的重量
     * @param value   物品的价值
     * @param bagSize 背包的容量
     */
    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){

        // 创建dp数组
        int goods = weight.length;  // 获取物品的数量
        int[][] dp = new int[goods][bagSize + 1];

        // 初始化dp数组
        // 创建数组后，其中默认的值就是0
        for (int j = weight[0]; j <= bagSize; j++) {
            dp[0][j] = value[0];
        }

        // 填充dp数组
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <= bagSize; j++) {
                if (j < weight[i]) {
                    /**
                     * 当前背包的容量都没有当前物品i大的时候，是不放物品i的
                     * 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
                     */
                    dp[i][j] = dp[i-1][j];
                } else {
                    /**
                     * 当前背包的容量可以放下物品i
                     * 那么此时分两种情况：
                     *    1、不放物品i
                     *    2、放物品i
                     * 比较这两种情况下，哪种背包中物品的最大价值最大
                     */
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
                }
            }
        }

        // 打印dp数组
        for (int i = 0; i < goods; i++) {
            for (int j = 0; j <= bagSize; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println("\n");
        }
    }
}

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

二、一维dp数组01背包（滚动数组）

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了dp[j]

需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

2.1 确定dp数组以及下标的含义

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

2.2 确定递推公式

此时dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，相当于 二维dp数组中的dp[i-1][j- weight[i]] + value[i]，即放物品i，一定是取最大的，毕竟是求最大价值，

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

2.3 初始化

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。

如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。

2.4 遍历顺序（重要）

for(int i = 0; i < weight.length; i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}
1
2
3
4
5

二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。
倒序遍历的原因：是为了保证物品i只被放入一次。

• 问题一：为什么倒序遍历？

举例：
物品0的重量weight[0] = 1，价值value[0] = 15
正序遍历：dp[0] = 0;
dp[1] = Math.max(dp[1], dp[1-weight[0]]+value[0]) = 15; （dp数组已经都初始化为0）
dp[2] = Math.max(dp[2] , dp[2-weight[0]]+value[0]) = 30; （dp数组已经都初始化为0）
也就是说物品0又被放进去一次，所以不能正序遍历。

为什么倒序遍历可以？
倒序遍历：先求dp[2]
dp[2] = Math.max(dp[2] , dp[2-weight[0]]+value[0]) = 15; （dp数组已经都初始化为0）
dp[1] = Math.max(dp[1], dp[1-weight[0]]+value[0]) = 15; （dp数组已经都初始化为0）

• 问题二：为什么二维dp数组历的时候不用倒序？
  因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！

• 问题三：可不可以先遍历背包容量嵌套遍历物品呢？
  不可以
  如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

2.5推导dp数组

2.6 完整代码

    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWight = 4;
        testWeightBagProblem(weight, value, bagWight);
    }

    public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
        int wLen = weight.length;
        //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
        int[] dp = new int[bagWeight + 1];
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 0; i < wLen; i++){
            for (int j = bagWeight; j >= weight[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        //打印dp数组
        for (int j = 0; j <= bagWeight; j++){
            System.out.print(dp[j] + " ");
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

总结

使用一维dp数组的写法，比较直观简洁，而且空间复杂度还降了一个数量级！