完全背包与多重背包
上篇文章我们说的 0-1背包问题，限定每样物品要么不取，取的话只能取 1 件
今天的完全背包问题(unbounded knapsack problem)：顾名思义，对所取物品的数量没有限制，可以取到无限多(背包容量有限)
思路初探
那么我们该如何处理这种完全背包问题呢？
我们还是拿出上一篇 0-1 背包问题最后的那个例子
我们根据 0-1 背包问题的状态转移方程最后得出了整个dp数组的取值：
根据dp数组的定义，我们知道最后的dp[4] [6]即为这组数据的所求
但是如果这个问题没有只取 1 件的限制
即，如果这个问题变成完全背包问题，那么最后的答案还对吗？
背包容量为：6
物品的价值与质量分别为：
V,W
6,4
2,5
1,4
8,1
显而易见，最大价值应为：装入 6 个第四个物品，总价值为：6 x 8 = 48
我们发现如果不限制取件数量，得出的答案和之前是不一样的
那么，即 0-1背包问题 的状态转移方程并不适用于完全背包问题
完全背包问题
思路一
思考，完全背包问题的状态转移方程应该是怎样？
我们的状态定义依旧不变，即dp数组含义依旧为：
dp[i] [w] 表示：对于前i个物品，当前背包的容量为w，这种情况下可以装的最大价值是dp[i][w]
那么我们肯定要适当地修改状态转移方程
我们在思考 0-1背包问题的时候，思考了以下两种情况：
Option A:
- 要么不装入第 i 件物品：即我们直接继承dp[i-1] [W]：
dp[i][W] =dp[i-1][W]; //继承上一个结果
Option B:
- 要么装入第 i 件物品：那么当前的dp[i] [W]：
//在“上一个结果价值”和“把当前第i个物品装入背包里所得到价值”二者里选价值较大的
dp[i][W] =Math.max(dp[i-1][W],dp[i-1][W-wt[i]] +val[i])
我们的第一种情况依旧相同
第二种情况稍有变化，我们思考：
装入第i种物品，此时和01背包不太一样，因为每种物品有无限个（但注意书包限重是有限的），所以此时不应该转移到dp[i−1][W−wt[i]]而应该转移到dp[i][W−wt[i]]，即装入第i种商品后还可以再继续装入第i种商品。
所以选择装入第 i 件物品的时候，我们的状态转移方程应为：
dp[i][W] =Math.max(dp[i-1][W],dp[i][W-wt[i]] +val[i])
所以完全背包问题的状态转移方程与 0-1背包唯一不同就是max的第二项由dp[i-1] 改为了 dp[i]
思路二
现在我们换个角度再次思考这个问题，
0-1背包问题里，物品只能取 0 件或 1 件
而完全背包里，我们的物品可以取 0 件，1 件，2 件，.....直到超过背包容量
我们定义的dp[i] [W]数组，W即为当前背包的容量
某一个物品的重量为wt[i]，那么在当前背包容量为W下
可装入的此物品数量就应该为：k = W/wt[i]
那么按照装入某物品数量的多少，再结合上述状态转移关系，就可以适当修改思路一的状态转移方程：
dp[i] [W] = Math.max(dp[i-1] [W - k*wt[i]] + k * val[i]) (对得到的每一个k进行循环)，也可以写成：
intk=W/wt[i];
for(intk=0; k<W/wt[i];k++){
dp[i] [W] =Math.max(dp[i-1] [W-k*wt[i]] +k*val[i]);
}
现在我们又引入了 k 层这一层循环
结合我们上一节 0-1背包问题最后的代码，有两层循环还记得吗？
外边一层 i 用来遍历物品
里边一层 j 用来遍历重量W
//外层循环遍历物品
for(inti=1;i<=N;i++){
//内层循环遍历1~W(背包容量)
for(intj=0;j<=W;j++){
//外层循环i,如果第i个物品质量大于当前背包容量
if (wt[i] >W) {
dp[i][W] =dp[i-1][W]; //继承上一个结果
} else {
//在“上一个结果价值”和“把当前第i个物品装入背包里所得到价值”二者里选价值较大的
dp[i][W] =Math.max(dp[i-1][W],dp[i-1][W-wt[i]] +val[i])
}
}
}
记得回顾一下前文噢
那么们由此再结合遍历k(所装物品数量)层的这层循环，即可得出完全背包问题思路二的代码：
//外层循环遍历物品
for(inti=1;i<=N;i++){
//内层循环遍历1~W(背包容量)
for(intj=0;j<=W;j++){
//外层循环i,如果第i个物品质量大于当前背包容量
if (wt[i] >W) {
dp[i][W] =dp[i-1][W]; //继承上一个结果
} else {
intk=W/wt[i]; //某一个物品的重量为wt[i]，那么在当前背包容量为W下,可装入此物品的数量
for(intk=0; k<W/wt[i];k++){
if(dp[i][W] <dp[i-1] [W-k*wt[i]] +k*val[i])//存储装多少个即哪个k，价值最大
dp[i][W] = (dp[i-1] [W-k*wt[i]] +k*val[i]);
}
}
}
}
只不过思路二的时间复杂度略高，有三层循环，我们可以分析出其时间复杂度为：
$$
O(N*W*k)
$$
多重背包
那么我们紧接着来看多重背包问题
多重背包（bounded knapsack problem）与前面不同就是每种物品是有限个：一共有 N 种物品，第 i（i从1开始）种物品的数量为 n[i]，重量为 wt[i]，价值为 val[i]。
在总重量不超过背包承载上限 W 的情况下，能够装入背包的最大价值是多少？
思路一
只是多了一个数组参数而言，这个数组 n[i] 里存放的就是第 i 件物品的数量，那么这个问题就很好处理了
我们由上文已经得出了：
当物品数量可以取无限的时候，即可以取k = W/wt[i]（备注：一定搞清楚，可以无限取，但是也要在不超过背包容量的前提下)
而多重背包问题里，人家直接给定了某件物品 i 的可取数量 n[i]
我们算出可以取无限的情况的总数量(不超过背包容量前提下可取的数量 k)：
k = W/wt[i]
然后再和给定的 n[i]，二者里取一个最小值不就行了？
k <= min(n[i], W/wt[i]) //k为装入第i种物品的件数,
那么我们大体的代码就和完全背包差不多，只是稍作修改即可：
//外层循环遍历物品
for(inti=1;i<=N;i++){
//内层循环遍历1~W(背包容量)
for(intj=0;j<=W;j++){
//外层循环i,如果第i个物品质量大于当前背包容量
if (wt[i] >W) {
dp[i][W] =dp[i-1][W]; //继承上一个结果
} else {
intk=W/wt[i]; //某一个物品的重量为wt[i]，那么在当前背包容量为W下,可装入此物品的数量
k=Math.min(k,n[i]); //往这儿看，变化在这里，多加的一行，取二者里的最小值
for(intk=0; k<W/wt[i];k++){
if(dp[i][W] <dp[i-1] [W-k*wt[i]] +k*val[i])//存储装多少个即哪个k，价值最大
dp[i][W] = (dp[i-1] [W-k*wt[i]] +k*val[i]);
}
}
}
}
时间复杂度依旧为：
$$
O(N*W*k)
$$
其实对于完全背包问题和多重背包，还有一种思路就是将其转换为 0-1 背包问题：
把第i种物品换成n[i]件01背包中的物品，则得到了物品数为
$$
Σn[i]
$$
的01背包问题
但这么拆分未免增加了问题的复杂程度...
完全背包和多重背包其实还有很多可以优化的地方和更高效的办法
但鉴于文章篇幅有限，我们的文章是从0到1带领读者先让大家详细的了解概况和介绍最基本最好想到的解决算法
优化和更好的办法大家可以基于此篇的基础上再去了解或阅读后续优化相关的文章
这里在此不再累赘。
那么今天的内容就到这儿，关于背包问题请大家一定反复阅读理解这两篇文章，加深印象，理清脉络，再去刻意练习
相信会对动态规划有更深入的理解
后续优化相关内容，我们下期再说
