1. 引入
之前做01背包都是用的二维dp数组，如果是二维dp数组，那么用到的是上方和左上方的数据。
可以发现当我们要计算i+1这行数据时，i-1这行的数据就用不到了。
也就是说，第i行第j个状态只和第i-1行第j个状态、第i-1行第j-weight[i]个状态有关。
那么我们就可以把i这个维度压缩掉，只留下j这个维度：
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
//对比上面的式子 其实就是把[i-1]这个维度去掉了
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i]);
再分析一次：
等式左边的dp[j]压缩的是dp[i][j]，代表第i层的dp；
等式右边的dp[j]和dp[j - weight[i]]代表第i-1层的dp
而我们使用for循环时枚举物品，也就是'i'这一维度的时候是正序的，即从1到2，从2到3...从i-1到i。
也就是：用i-1状态的一维dp数组作为i状态的一维dp数组的初值（因为i状态只和i-1状态有关），因此被称为滚动数组。
2. 分析
2.1 确定dp数组的意义
dp[j]表示，容量为j的背包，所能承载的编号为0至i-1物品的最大价值。（注意dp[j]只考虑前i-1个物品，不放第i件时）
2.2 状态转移方程
当我们来到dp[j]时，dp[j]里的值就是上一层dp的值。
两个选择：
-
不放物品i
不放物品那容量也就不变，价值自然也不变了，还是dp[j] -
放物品i
放物品那就是容量减少，价值增加：dp[j - weight[i]] + value[i]
因此也就可以得出如上的状态转移方程，相当于去掉了dp[i][j]中i的维度
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
2.3 初始化
首先可以确定dp[0] = 0，因为容量为0的背包装不了东西，价值肯定是0。
那么其他位置呢，首先不能像二维数组那样初始完两条边后剩下的随便初始化都行，因为二维数组中间的位置的值都是由左上方和上方的值得来的，自己的初始值肯定会被覆盖掉。
而一维数组中dp[j]是通过dp[j]和dp[j-weight[i]]推导过来的，而且接下来还要取max值，因此所有数全部初始化为0，否则会出现max值被初始值覆盖的问题。
2.4 遍历
先上代码
function bag01Problem(weight, value, load) {
const len = weight.length;
//遍历物品
for (let i = 0; i < len; i++) {
//遍历背包容量
for (let j = load; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j] - weight[i] + value[i]);
}
}
}
两个注意点：
（1）背包容量要倒序遍历
倒序遍历是为了保证物品i只被放入一次，如果选择正序遍历，那么物品0就会被重复加入多次。
举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15
如果正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。
为什么倒序遍历，就可以保证物品只放入一次呢？
倒序就是先算dp[5]
dp[5] = dp[5 - weight[0]] + value[0] = dp[4] + value[0] = 15 （dp数组已经都初始化为0）
dp[4] = dp[3] + value[0] = 15
所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。
二维数组不用倒叙遍历，是因为自身数据都是由上方和左上方计算得来，本层的dp[i][j]不会被覆盖。
（2）for循环顺序不能变
因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。
因为滚动数组的特性，我们必须先将i-1这层的j全部遍历完，然后再进到第i层把dp[i-1][j]的数据赋值给dp[i][j]，然后第i层才开始根据赋值过来的数据和状态转移公式进行计算。
最后附上完整代码：
function testWeightBagProblem(weight, value, load) {
const len = wight.length;
const dp = new Array(load + 1).fill(0);
for (let i = 0; i < len; i++) {
for (let j = load; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j] , dp[j - wight[i]] + value[i]);
}
}
return dp[load];
}
function test() {
console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
}
test();