算法-01背包-二维DP数组

1. 引入

背包问题应该是dp中最经典的问题之一，主要掌握01背包和完全背包即可。01背包的特点是每个物品只能用一次，而完全背包的特点是物品可以用无数次。

本文中用这个例子讲解：

背包最大承重load为4

物品的数据如下

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

2.分析

分析dp题目还是按经典的流程走：

2.1 确定dp数组含义

本文中先分析比较好理解的二维dp数组：

dp[i][j]表示从下标为0-i的物品中任意取出物品，放到容量为j的背包中，能产生的最大价值是多少。

（其实和题目一个意思，只不过物品数量和背包容量在变）

2.2 确定状态转移方程

两个选择：

• 放不下物品i
  当物品重量大于背包承重，物品无法放入背包中，也就是说取物品时不取它了，那么dp[i][j] = dp[i-1][j]

• 能放下物品i
  就算能放下，也可以选择放或者不放，那么就是选择其中可以创造更多价值的放法，容易得出dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

2.3 初始化

二维数组的初始化一般就是初始第一行和第一列

初始化第一列

            //填充dp[i][0] 背包容量为0 放不了东西 价值肯定为0
            for (let i = 0; i < len; i++) {
                dp[i][0] = 0;//可以不写 因为初始化二维数组已经为0了
            }

初始化第一行

            //填充dp[0][j] 背包容量小于物品0时 放不了东西
            for (let j = 0; j < weight[0]; j++) {
                dp[0][j] = 0;//可以不写 因为初始化二维数组已经为0了
            }

            //填充dp[0][j] 背包容量大于物品0时 放物品0进去
            for (let j = weight[0]; j <= load; j++) {
                dp[0][j] = value[0];
            }

但是可以注意到，前两个循环都是将数值设置成0，所以其实在建立二维数组时将所有数字初始化成0就不用写那两个循环了，留下最后一个就行。

2.4 遍历并返回

先遍历物品，一个个尝试物品i对应不同负重j时要不要放进去。
（先遍历背包负重也是可以的，原因是递推公式中，dp的值都是由左上方或上方的值推导而来的，因此横着遍历和竖着遍历是一样的 看第22分钟左右）

            //状态转移方程
            for (let i = 1; i < len; i++) {
                for (let j = 1; j <= load; 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]);
                    }
                }
            }

返回最终值

            return dp[len - 1][load]; 

最后有完整代码

        //weight是物品的重量 value是物品的价值 load是背包容量
        function bag01Problem(weight, value, load) {
            const len = weight.length;
            //dp[i][j]表示从0-i的物品里取，放到容量为j的背包中，价值总和最大为多少
            const dp = new Array(len).fill().map(item => Array(load + 1).fill(0));

            //初始化 背包容量大于物品0时 放物品0进去
            for (let j = weight[0]; j <= load; j++) {
                dp[0][j] = value[0];
            }

            //状态转移方程
            for (let i = 1; i < len; i++) {
                for (let j = 1; j <= load; 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]);
                    }
                }
            }
            return dp[len - 1][load];
        }
        function test() {
            console.log(bag01Problem([1, 3, 4, 5], [15, 20, 30, 55], 6));
        }

        test(); //70