1、什么是完全背包问题？
01背包问题：有一个背包的容积为V，有N个物品，每个物品的体积为v[i]，权重为w[i]，每个物品只能取1次放入背包中，背包所有物品权重和最大是多少？
完全背包 ：有一个背包的容积为V，有N个物品，每个物品的体积为v[i]，权重为w[i]，每个物品可以取无限次放入背包中，背包所有物品权重和最大是多少？
01背包问题和完全背包问题的区别就在于，每个物品取的最大次数是1次还是无限次。
2、动态规划的状态和转移方程
参考01背包的状态和转移方程，来推导完全背包的状态和转移方程。
大家可以留出5秒钟的时间来思考…
恭喜你，完全背包问题已经被你攻克了，下面来看一下代码吧。
3、代码
练习题：完全背包问题
程序：
代码优化
优化点：
黄金级：
1）if (v[i] > j) 可以优化到 for (int j = 1; j <= m; j ++ ) 中，优化后为：
2）w[] 和 v[]可以优化掉。代码中的v和w数组使用仅限于i状态下，因此，可以定义两个变量，v和w，在for (int i = 1; i <= n; i ++ )中输入即可，优化后：
for (int i = 1; i <= n; i ++ ) {
int v, w;
scanf("%d %d", &v, &w);
}
铂金级：
二维数组f可以优化成一维的f，具体优化可以参考这篇文章，这里不过多介绍。
王者级：：
从状态转移方程下手：f[i][j] = max(f[i-1][j- k * v[i]]+ k * w[i] (k= 0, 1, 2, 3, 4,…))
方程拆开：
使用代入法，将j= j-v[i]带入上面的方程中得到：
对比第二个和第一个方程，我们发现，方程1可以简化成：
怎么看起来跟01背包模型的好像啊，我们对比一下：
好了，上最终的代码了：
16行代码解决该问题，如果有疑问或者不懂的地方欢迎评论区留言。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/5474.html