一维数组0-1背包问题理论基础
首先明确变量含义
i是物品
j是容量
二维dp【】【】数组的递推公式
dp【i】【j】=Math.max（dp【i-1】【j】，dp【i-1】【j-weight【i】】+value【i】）
i是物品
就是背包容量
dp【i】【j】的含义
使用0-i这个位置的物品装满容量为j的背包的最大价值
也就是，使用i以及i下标之前的物品，装满容量为j的背包的最大价值为【i】【j】
一维dp【】数组
确定dp【】数组含义
dp【j】表示容量为j的背包能装的最大价值为dp【j】
确定递推公式
不放物品i：
dp【j】
为什么是第dp【j】？
我们之前不二维数组是dp【i-1】【j】，我们压缩成一维数组就是dp【j】了
放物品i：
dp【j-weight【i】】+value【i】
递推公式：
dp【j】=Math.max（dp【j】，dp【j-weight【i】】+value【i】）
初始化
零下标
dp【0】=0
因为装满背包为0的物品的最大价值就是0
非0下标
根据使用min还是max
来决定初始化成Integer.MAX_VALUE还是Integer.MIN_VALUE
遍历顺序（必须是倒序）
我们要倒序遍历
for(i=0;i<物品数量；i++)
for(j=bagweight;j>=weight【i】;j--)
dp【j】=Math.max（dp【j】，dp【j-weight【i】】+value【i】）倒序遍历的目的：防止物品被重复添加，保证每个物品只被添加一次
为什么不能正序遍历
我们之前二维数组的图是这样的
重量 价值
物品0 1 15
物品1 3 20
物品2 4 30
背包容量 j 0 1 2 3 4
物品 i
物品0 0 15 15 15 15
物品1 0
物品2 0
我们一维数组来从左往右正序遍历试一下？
for (let i = 0; i < 物品数量; i++)
for (let j = weight[i]; j <= bagweight; j++)
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
dp【1】=dp【1-1】+15=dp【0】+15=15
dp【2】=dp【2-1】+15=dp【1】+15=30
不对啊？我们的物品0应该只被添加一次
我们1-4的价值应该都是15才对为啥会这样呢？
看看我们的倒序遍历
for(i=0;i<物品数量；i++)
for(j=bagweight;j>=weight【i】;j--)
dp【j】=Math.max（dp【j】，dp【j-weight【i】】+value【i】）dp【2】=dp【2-1】+15=dp【1】+15=15
dp【1】=dp【1-1】+15=dp【0】+15=15
我们保证了我们的物品只被添加了一次
为什么会一维数组会出现正序倒序交换出错而二维数组不会？
因为我们的二维数组dp【i】【j】我们是从上一层推出来的
我们是从左上方往右下方推出来的
我们的节点不会覆盖+重复利用
而一维数组dp【n】我们是复用同一层的n个数字
所以我们要讲究遍历顺序