0-1 背包

给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wight[i]，价值为value[i]，现在让你用这个背包装物品，最多能装的价值是多少？
举个简单的例子，输入如下：

N = 3, W = 4
wight = [2, 1, 3]
value = [4, 2, 3]

算法返回 6，选择前两件物品装进背包，总重量 3 小于W，可以获得最大价值 6。
第一步要明确两点，「状态」和「选择」。所以状态有两个，就是「背包的容量」和「可选择的物品」。
第二步要明确**dp**数组的定义。
dp[i][w]的定义如下：对于前i个物品，当前背包容量为w的情况下可以获得的最大价值为**dp[i][w]**。
根据这个定义，我们想求的最终答案就是dp[N][W]。base case 就是dp[0][..] = dp[..][0] = 0，因为没有物品或者背包没有空间的时候，能装的最大价值就是 0。
第三步，根据「选择」，思考状态转移的逻辑。
如果你没有把这第i个物品装入背包，那么很显然，最大价值dp[i][w]应该等于dp[i-1][w]。你不装嘛，那就继承之前的结果。
如果你把这第i个物品装入了背包，那么dp[i][w]应该等于dp[i-1][w-wight[i]] + value[i]。装入第i个，容量减去wight[i]，价值加上value[i]。
状态压缩：
dp[i][j]的值只与dp[i-1][0,...,j-1]有关，所以我们可以采用动态规划常用的方法（滚动数组）对空间进行优化（即去掉dp的第一维）。需要注意的是，为了防止上一层循环的dp[0,...,j-1]被覆盖，循环的时候 j 只能逆向枚举，得到dp[j] = max(dp[j], dp[j−w[i]]+v[i])

0-1背包的模版

let dp = new Array(m + 1).fill('');
// 每个物品的质量
for (let num of nums) {
      // 从目标倒序遍历到该物品的质量
    for (let j = target; j >= num; j--) {
        /* 递推式
        dp[j]=Math.max(dp[j],dp[j-num]+1);
        dp[j]=dp[j]+dp[j-num];
        */
    }
}
return dp[target];

完全背包

完全背包（unbounded knapsack problem）与01背包不同就是每种物品可以有无限多个：一共有N种物品，每种物品有无限多个，第i（i从1开始）种物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
dp[i][w]的定义：
对于前i个物品，当前背包容量为w的情况下可以获得的最大价值为dp[i][w]。
转移方程：
1.不装入：dp[i][w]=dp[i-1][w]
2.装入：dp[i][w]=dp[i][w-wight[i]]+value[i]

// 装入当前这个，因此指针i不后移
dp[i][j] = max(dp[i−1][j], dp[i][j−w[i]]+v[i])         // j >= w[i]

注意这个与0-1背包是不同的，0-1背包的装入方程为dp[i][j] = dp[i-1][j−w[i]]+v[i]，0-1背包物品选择不能重复，完全背包物品选择可以重复。
状态压缩：
和01背包问题类似，也可进行空间优化，优化后不同点在于这里的 j 只能正向枚举而01背包只能逆向枚举，因为这里的max第二项是dp[i]而01背包是dp[i-1]，即这里就是需要覆盖而01背包需要避免覆盖，得到dp[j] = max(dp[j], dp[j−w[i]]+v[i])

多重背包

多重背包（bounded knapsack problem）与前面不同就是每种物品是有限个：一共有 N 种物品，第i（i从1开始）种物品的数量为n[i]，重量为wt[i]，价值为val[i]。在总重量不超过背包承载上限 W 的情况下，能够装入背包的最大价值是多少？
dp[i][w]的定义：
对于前i个物品，当前背包容量为w的情况下可以获得的最大价值为dp[i][w]。
转移方程：
1.不装入：dp[i][w] = dp[i-1][w]
2.装入：dp[i][w]``** = **``dp[i -1][w - k * wt[i - 1]]+ k * val[i - 1]。把物品 i 装入背包时因为每种物品都有自己的数量限制，我们需要在可行的数量中找出最大的价值。

dp[i][w] = max(dp[i-1][w], dp[i - 1][w - k * wt[i - 1]]+ k * val[i - 1])

状态压缩：dp[j] = max(dp[j], dp[j−k*w[i]]+k*v[i])

对比