P02: 完全背包问题
题目
有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
基本思路
这个问题非常类似于01背包问题,所 不同的是每种物品有无限件。也就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取0件、取1件、取2件……等很多种。如果仍然按照解 01背包时的思路,令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程,像这样:
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
这跟01背包问题一样有O(VN)个状态需要求解,但求解每个状态的时间已经不是常数了,求解状态f[i][v]的时间是O(v/c[i]),总的复杂度可以认为是O(V*Σ(V/c[i])),是比较大的。
将01背包问题的基本思路加以改进,得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要,可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。
一个简单有效的优化
完全背包问题有一个很简单有效的优化,是这样的:若两件物品i、j满足c[i]<=c[j]且w[i]& gt;=w[j],则将物品j去掉,不用考虑。这个优化的正确性显然:任何情况下都可将价值小费用高得j换成物美价廉的i,得到至少不会更差的方案。对于 随机生成的数据,这个方法往往会大大减少物品的件数,从而加快速度。然而这个并不能改善最坏情况的复杂度,因为有可能特别设计的数据可以一件物品也去不掉。
这个优化可以简单的O(N^2)地实现,一般都可以承受。另外,针对背包问题而言,比较不错的一种方法是:首先将费用大于V的物品去掉,然后使用类似计数排序的做法,计算出费用相同的物品中价值最高的是哪个,可以O(V+N)地完成这个优化。这个不太重要的过程就不给出伪代码了,希望你能独立思考写 出伪代码或程序。
转化为01背包问题求解
既然01背包问题是最基本的背包问题,那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是,考虑到第i种物品最多选V/c[i]件,于是可以把第i种物品转化为V/c[i]件费用及价值均不变的物品,然后求解这个01背包问题。这样完全没有改进基本 思路的时间复杂度,但这毕竟给了我们将完全背包问题转化为01背包问题的思路:将一种物品拆成多件物品。
更高效的转化方法是:把第i种物品拆成费用为c[i]*2^k、价值为w[i]*2^k的若干件物品,其中k满足c[i]*2^k<=V
。这是二进制的思想,因为不管最优策略选几件第i种物品,总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log V/c[i])件物品,是一个很大的改进。
但我们有更优的O(VN)的算法。
O(VN)的算法
这个算法使用一维数组,先看伪代码:
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-cost]+weight}
你会发现,这个伪代码与P01的伪代码只有v的循环次序不同而已。 为什么这样一改就可行呢?首先想想为什么P01中要按照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]}
将这个方程用一维数组实现,便得到了上面的伪代码。
最后抽象出处理一件完全背包类物品的过程伪代码:
procedure CompletePack(cost,weight)
for v=cost..V
f[v]=max{f[v],f[v-c[i]]+w[i]}
总结
完全背包问题也是一个相当基础的背包问题,它有两个状态转移方程,分别在“基本思路”以及“O(VN)的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会,不仅记住,也要弄明白它们是怎么得出来的,最好能够自己想一种得到这些方程的方法。事实上,对每一 道动态规划题目都思考其方程的意义以及如何得来,是加深对动态规划的理解、提高动态规划功力的好方法。
分享到:
相关推荐
背包九讲: P01:01背包问题 P02:完全背包问题 P03:多重背包问题 P04:混合三种背包问题 P05:二维费用的背包问题 P06:分组的背包问题 P07:有依赖的背包问题 P08:泛化物品 P09:背包问题问法的变化
背包问题: 01背包问题 02: 完全背包问题 03: 多重背包问题 04: 混合三种背包问题 05: 二维费用的背包问题 06: 分组的背包问题 07: 有依赖的背包问题 08: 泛化物品 09: 背包问题问法的变化 11: 背包问题的搜索解法
P01: 01背包问题 2 题目 2 基本思路 2 优化空间复杂度 2 初始化的细节问题 3 一个常数优化 4 ...P02: 完全背包问题 4 题目 4 基本思路 5 一个简单有效的优化 5 转化为01背包问题求解 5 O(VN)的算法 6 总结 6
实验目的:0/1背包问题的回溯算法设计 实验原理:回溯算法设计。 实验要求:基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想: 0-1背包问题:给定n种物品和一背包.物品i的...
算法-动态规划- 背包问题 P02- 完全背包(包含源程序).rar
程序设计:01背包问题.doc
第1讲:背包问题 第二讲:完全背包问题 第3讲:多重背包问题 第4讲:混合三种背包问题 共9讲
95、1268:【例9.12】完全背包问题(2020.03.19)A
详细的完全背包问题1的C语言代码
动态规划之完全背包问题。 完全背包是在N种物品中选取若干件(同一种物品可多次选取)放在空间为V的背包里,每种物品的体积为C1,C2,…,Cn,与之相对应的价值为W1,W2,…,Wn.求解怎么装物品可使背包里物品总价值...
背包问题九讲中的完全背包问题的三种算法的具体java实现代码。
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最...
完全背包问题N件物品放入容量为C的背包。第i件物品的费用(重量、体积等)为wi,价值为vi。每件物品可以取用任意多次(无限数量),选择将哪些物品放入背包令总费用不超过背包的容量且物品的价值总和最大。输入格式...
基于线性规划解决二重约束完全背包问题,c++代码。实现功能: 输入: 1、背包容量V质量M和物品数量n 2、//每个物品的容量v[i]和质量m[i] 输出: 最大value
C++实现。对0/1背包问题应用3种方法(动态规划、...对背包问题和完全背包问题应用动态规划和贪婪算法,通过实例比较求解速度。 随机生成500个0/1背包问题(问题规模可以相对较小),使用贪心算法和动态规划进行求解。
.net可视化的背包问题,使用了asp:table控件,能够进行动态的添加行,完全是在服务器端执行的。希望能帮助需要帮助的人。
背包之01背包、完全背包、多重背包详解.
01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下: 给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择...
背包问题九讲(包含01背包,多重背包,完全背包等)
动规经典:01背包.cpp