“0-1背包问题” 深究

背景

46. 携带研究材料（第六期模拟笔试）是一道很经典的 0-1 背包问题。接下来我们将分别讨论dp数组为2维和1维的两种解法（这里先说2维是因为2维简单）。卡码网是ACM模式，代码为 nodejs，需要先处理输入

1、二维dp数组

二维dp递推公式

`dp[i][j]` 当最大背包空间为j时，装 `0 - i` 个物品所得到的最大价值

if (weigth[i] > j）{
    // 当前背包大小放不下当前物品
    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. 二维dp初始化

初始化时是需要处理最左列和最上行，其中最上行需记录容量从小到大过程中 `dp[0][j]` 的值，最左列因为 `j = 0` 即容量为0，所以 `dp[i][0]` 均为0

2. 二维dp遍历顺序

常规是先遍历物品，后遍历容量。实际反过来也是可以的。因为根据递推公式来看，新的 `dp[i][j]` 是由dp数组左上角求得，所以也可以先遍历容量

2、一维dp数组

1. 一维dp递推公式

受二维递推公式启发，新行 i 中的值都是由上一行 `i - 1` 的值生成，所以直接在一行的基础上覆盖即可

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

2. 只修改了递推公式，仍用顺序遍历，出错了

于是我就直接在二维代码基础上改了一下递推公式就提交了，答案错误

for (let tempWeight = 0; tempWeight <= bagWeight; tempWeight ++) {
    if (tempWeight >= weight[0]) {
        dp[tempWeight] = value[0]
    }
}    

for (let i = 1; i < types; i ++) {
    for (let j = 1; j <= bagWeight ; j ++) {
        if (weight[i] > j) {
            //放不下
            continue
        } else {
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
        }
    }
}

3. 顺序遍历为什么错？

初始化还是正确的，等价于对原二维dp的第一行进行初始化，也就是对第0个物品在递增的容量下价值的初始化。随后从第1个物品开始递推，到这里没问题。我们选一个样例来模拟，排查一下错误：

背包最大重量 `bagWeight = 3`，物品数 `types = 3`

weight数组

物品 0 物品 1 物品 2
weight 1 1 3
value 15 20 25

初始化 dp（相当于 i = 0）：

0 1 2 3
0 15 15 15

i = 1：此时出了问题

0 1 2 3
0 20 40 60

dp[1] = Math.max(dp[1], dp[1 - 1] + 15) = Math.max(15, 0 + 20) = 20

dp[2] = Math.max(dp[2], dp[2 - 1] + 20) = Math.max(15, 20 + 20) = 40 ，但是dp[2]应该是 15 + 20 = 35

出岔子了，因为是对dp顺序遍历，dp[j - weight[i]] 被更新过了，现在是包含了当前物品，又加上了一个当前物品，即 `value[i]` ，此时物品1被同时放入背包两次，违背了每个物品只能放入背包一次的设定

后面就会知道，顺序遍历就是完全背包，一个物品可以多次被放入背包中

4. 先对初始化整合一下吧

前面的初始化是先对物品0进行遍历初始化，随后我们再从对物品1开始对dp进行迭代。能不能把 `i = 0` 也扔到迭代里面呢？

对dp的初始化，需要根据dp数组的定义来进行

dp[0]当然为0，因为容量为零时放不下物品，价值自然就是0。那么dp[1]、dp[2] ... ... 怎么办呢？

重新观察递推公式：

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

当后续我们对每个物品遍历背包大小的时，若背包足够大能放下当前物品时，起到更新作用的是 `dp[j - weight[i]] + value[i]` ，那我们自然这项更大，则dp[i]就应该足够小，初始化为0

5. 逆序遍历为什么对？

顺序遍历错就错在对一个物品多次放入背包，而实际只能放一次

用逆序时，是先用大空间来放物品，此时由于索引 `j - weight[i] < j`，所以 dp[j - weight[i]] 尚未被更新，放的可能是之前上一轮放的物品，至少不会放这一轮的物品。对前面的测试用例走一遍就有感受了

背包最大重量 bagWeight = 3，物品数 types = 3

weight数组

物品 0 物品 1 物品 2
weight 1 1 3
value 15 20 25

初始化 dp：

0 1 2 3
0 0 0 0

i = 0，weight[i] = 1，value[i] = 15，注意这个表是从右往左填：

0 1 2 3
0 15 15 15

i = 1，weight[i] = 1，value[i] = 20：

0 1 2 3
0 20 35 35

i = 2，weight[i] = 3，value[i] = 25：

0 1 2 3
0 20 35 35

很成功，如果顺序遍历，后面容量大时需要前面的dp，而前面的dp已经被更新过，可能已经放入了当给物品，于是会出现多次放入同一物品。逆序就不会

6. 一维dp遍历顺序
当使用一维dp时，先遍历物品还是先遍历容量有讲究吗？有，只能先遍历物品，因为一维dp是依赖每次物品可选范围新增一个进行更新的，也就是一行一行遍历

7. 最终代码
let dp = Array.from({length: bagWeight + 1}, () => 0)

for (let j = bagWeight; j >= 0; j --) {
    for (let i = 0; i < types; i ++) {
        if (j < weight[i]) {
            continue
        } else {
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);    
        }
    }
}