01背包问题的理论基础

什么是01背包问题？

01背包问题可以概括为：有一个能够容纳固定重量的物体的背包和一系列重量的物体。物体i的重量为weight[i]，价值为value[i]。求在背包的容纳范围内，怎么样装才能使背包中的物体价值最高。

二维dp数组解法

第一步。明确dp数组的含义。二维解法中dp[i][j]表示从下标为[0-i]的物体中任意选取装入容量为j的背包，能够得到的最高价值为dp[i][j]。

第二步。求递推公式。动态规划的一个特点是这一状态可以由上一个状态推导而出，那dp[i][j]这个状态的上一个状态的不同是什么呢？不同之处在于物体i是否放进了背包，分为两种情况。

• 未放入。此时上一个状态为dp[i - 1][j]。这个状态还隐含的意思是，weight[i] > j，即该物体重量以及超过了背包容量。
• 放入。放入其实相当于包里提前就有了i物体，那么对应的上一个状态需要扣除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])

第三步。初始化可以看递推公式，一般来说二维数组需要考虑第一行和第一列的情况，第一行就是i = 0，背包里面只放下标0的物体时的价值；第一列就是背包容量为0的价值，自然是0。

第四步。遍历顺序本题都可以。先遍历物体和背包容量的结果是一致的。

最后来看看二维dp数组解法的代码

function testWeightBagProblem(weight, value, size) {
    //定义dp数组
    const dp = new Array(weight.length).fill(0).map(() => new Array(size + 1)).fill(0)
    //初始化dp数组
    //需要从能够装下weigth[0]的背包容量开始初始化！！！
    for (let j = weight[0]; j <= size; j++) {
        dp[0][j] = value[0]
    }
    //遍历
    for (let i = 1; i < weight.length; i++) {
        for (let j = 0; j <= size; j++) {
            //物体i不能放进背包
            if (weight[i] > j) dp[i][j] = dp[i - 1][j]
                //物体i能够放进背包
            else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i] + value[i]])
        }
    }
    return dp[weight.length - 1][size]
}

一维dp数组解法

第一步，明确dp数组含义。dp[j]表示容量为j的背包能够取到的最大价值为dp[j]。

第二步，递推公式。借鉴二维解法中的递推公式，依旧有物品i是否放入背包两种情况。放入，则dp[j] = dp[j - weight[i]]；如果不放入，则dp[j] = dp[j]，也即是上一轮循环的dp[j]。

第三步，初始化。一个很显然的问题，dp[0]必定是为0的。

第四步，遍历顺序。这是一维解法中最让人费解的地方。先给出代码

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

第一个问题，背包容量为何需要倒序遍历？

来看看如果是正序遍历会有什么问题。

dp[1] = dp[1 - weight[0]] + value[0] = 15 dp[2] = dp[2 - weight[0]] + value[0] = 30

这里相当于物品0被放入背包两次。其实可以从二维数组的角度来理解，dp[j]还是从[0, i]中选取物品放入背包的最大价值，第一行的计算式没有问题。但是第二行计算式，dp[2 - weight[0]]这里得到是dp[1]， 注意这里的dp[1]是物品0被放入背包得到的！！！而dp[2]计算的时候又再次把物品0放入了背包导致了重复放置。

换句话说，正序计算得到的dp[j]存在重复问题。那为什么二维解法就不会有这个问题？以及倒序为什么可以避免这个问题呢？

二维数组中dp[i][j]的值来源于dp[i - 1][j]，物品i只有在计算dp[i][j]的时候才有可能被放入，不存在重复问题。

倒序之所以能解决是因为，初始时dp数组都为0，计算dp[j]时可以保证不会用已经放入某个物体的背包的dp[j]来计算后续的dp[j]。

第二个问题，为什么需要先遍历物品，然后遍历背包容量？

因为如果先遍历背包容量，每个背包中就会只放入一个物品了！！！假设我们调换顺序，那么首先背包取到一个最大容量，然后开始遍历物品。按照递推公式，第一次遍历下来dp[j]等于放入一个物品后背包的价值；然后遍历第二个物品， 按照递推公式，第二次遍历得到的是只放入第二个物品时得到的最大价值dp[j]。因为这里变化的只有i，相当于背包中只放入一个物品。

function testWeightBagProblem(wight, value, size) {
    const len = wight.length
    const dp = Array(size + 1).fill(0);
    for(let i = 0; i <= len; i++) {
        for(let j = size; j >= wight[i]; j--) {
            dp[j] = Math.max(dp[j], value[i] + dp[j - wight[i]]);
        }
    }
    return dp[size];
}

function test () {  
    console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
}

test();