看这篇日志之前,请先阅读我的上一篇日志,关于0/1背包的问题。
完全背包问题的描述:
有N 种物品和一个容量为V 的背包,每种物品都有无限件可用。第i 种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
可能大家已经看出来了,完全背包问题其实就是在0/1背包的问题的基础上加了一个条件:每种物品都有无限件可用。
这个问题有不少解法,下面只给出最优化的O(VN)的算法。
这个算法使用一维数组,先看伪代码:
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-cost]+weight}
你会发现,这个伪代码与01背包的伪代码只有v 的循环次序不同而已。为什么这样一改就可行呢?首先想想为什么01背包中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说,这正是为了保证每件物品只选一次,保证在考虑“选入第i 件物品”这件策略时,依据的是一个绝无已经选入第i 件物品的子结果
f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件,所以在考虑“加选一件第i种物品”这种策略时,却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]],所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。值得一提的是,上面的伪代码中两层for循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。
这个算法也可以以另外的思路得出。
例如,将基本思路中求解f[i][v-c[i]]的状态转移方程显式地写出来:
f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}
把[i-1]和[i] 都去掉,就可以得到f[v]=max{f[v],f[v-c[i]]+w[i]}。为什么可以去掉呢。看一下上一篇日志中的这个图
你会发现,我们用二维数组 的解法做的时候,都是扣掉 当前的容量所剩下的容量最多能放多少,取的是上一行的数据: f[i-1][v],这是因为在当前背包加入的之前,上一行就表示出了 加入上一个背包时的最优解。而其实每一行都比上一行优化,因为每往下走一行,就加入了一个背包,比原来的选择多,得出的优化值自然比上一行的优化。
知道了每一行都比上一行优化之后 ,完全背包问题的答案就可以得出来了,我们每次都取当前行,即f[i][v],那么原状态方程就变成了:f[i][v]=max{f[i][v],f[i][v-c[i]]+w[i]},呵呵,二维数组的第一维都变成i了,就是说都在同一行进行比较了。这样的话就可以把它转化成一维数组问题了。即,直接把[i]去掉。。。
最后抽象出处理一件完全背包类物品的过程伪代码:
procedure CompletePack(cost,weight)
for v=cost..V
f[v]=max{f[v],f[v-c[i]]+w[i]}
分享到:
相关推荐
动态规划之完全背包问题。 完全背包是在N种物品中选取若干件(同一种物品可多次选取)放在空间为V的背包里,每种物品的体积为C1,C2,…,Cn,与之相对应的价值为W1,W2,…,Wn.求解怎么装物品可使背包里物品总价值...
详细的完全背包问题1的C语言代码
95、1268:【例9.12】完全背包问题(2020.03.19)A
基于线性规划解决二重约束完全背包问题,c++代码。实现功能: 输入: 1、背包容量V质量M和物品数量n 2、//每个物品的容量v[i]和质量m[i] 输出: 最大value
背包问题九讲中的完全背包问题的三种算法的具体java实现代码。
C++实现。对0/1背包问题应用3种方法(动态规划、...对背包问题和完全背包问题应用动态规划和贪婪算法,通过实例比较求解速度。 随机生成500个0/1背包问题(问题规模可以相对较小),使用贪心算法和动态规划进行求解。
完全背包问题.md
完全背包问题.docx
基于C++的完全背包问题(.cpp)
完全背包问题N件物品放入容量为C的背包。第i件物品的费用(重量、体积等)为wi,价值为vi。每件物品可以取用任意多次(无限数量),选择将哪些物品放入背包令总费用不超过背包的容量且物品的价值总和最大。输入格式...
.net可视化的背包问题,使用了asp:table控件,能够进行动态的添加行,完全是在服务器端执行的。希望能帮助需要帮助的人。
用于解决多维背包问题经典常规数据集,测试算法时候用
《背包问题九讲》,dd_engi大神原作,从属于《动态规划...2、完全背包问题;3、多重背包问题;4、混合三种背包问题;5、二维费用背包问题;6、分组的背包问题;7、有依赖的背包问题;8、泛化物品;9、背包问题的变化;
第二讲 完全背包问题 第二个基本的背包问题模型,每种物品可以放无限多次。 第三讲 多重背包问题 每种物品有一个固定的次数上限。 第四讲 混合三种背包问题 将前面三种简单的问题叠加成较复杂的问题。 第五讲 二...
背包问题: 01背包问题 02: 完全背包问题 03: 多重背包问题 04: 混合三种背包问题 05: 二维费用的背包问题 06: 分组的背包问题 07: 有依赖的背包问题 08: 泛化物品 09: 背包问题问法的变化 11: 背包问题的搜索解法
python解决背包 问题算法课程作业