403 Forbidden
Request forbidden by administrative rules.豆丁微信公众号
君，已阅读到文档的结尾了呢~~
[整理版]完整背包题目
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
[整理版]完整背包题目
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口& 完全背包
文章作者：Yx.Ac
& 文章来源：勇幸|Thinking ()
& 转载请注明，谢谢合作。
前面回顾了，在此基础上本节回顾完全背包的几种实现形式，主要有以下几方面内容：
==完全背包问题定义 & 基本实现
==完全背包二进制拆分思想
==完全背包使用滚动数组（略）
==完全背包中的逆向思维
==完全背包使用一维数组
========================================
完全背包问题定义 & 基本实现
问题：有个容量为V大小的背包，有很多不同重量weight[i](i=1..n)不同价值value[i](i=1..n)的货物，每种物品有无限件可用，想计算一下最多能放多少价值的货物。
与01背包不同的是，完全背包每件物体可以放入无限件（只要能放的下），故对于每件物品i，相当于拆分成了v/c[i]件相同的物品，拆分之后物品i就不是放入或不放入的两种情况了，而是放入0件、放入1件、放入2件…等情况了，对于该件物品i，最大价值取放入k件的最大值，故状态转移方程为：
f(i,v) = max{ f(i-1,v-k*c[i]) + k*w[i] | 0&=k&=v/c[i] }
各状态的意义不再赘述，上代码，关于复杂度以及每种物品的状态数见代码注释：
#include &iostream&
/* 完全背包 版本1
* Time Complexity
大于O(N*V)
* Space Complexity O(N*V)
* 设 V &= 200 N &= 10
* 状态转移方程：f(i,v) = max{ f(i-1,v-k*c[i]) + k*w[i] | 0&=k&=v/c[i]
* 每件物品有v/c[i]种状态
int maxV[11][201];
/* 记录子问题最优解，物品可重复 */
int weight[11];
int value[11];
void main()
scanf(&%d %d&,&V, &N);
for(i = 0; i & N; ++i)
scanf(&%d %d&,&weight[i],&value[i]);
for(i = 0; i & N; ++i)
for(j = 0; j &= V; ++j)
maxV[i][j] = maxV[i-1][j];
if(j/weight[i] &= 1)
int max_tmp = 0;
for(k = 1; k &= j/weight[i]; ++k)
if(maxV[i-1][j-k*weight[i]] + k*value[i] & max_tmp)
max_tmp = maxV[i-1][j-k*weight[i]] + k*value[i];
maxV[i][j] = maxV[i][j] & max_tmp ? maxV[i][j] : max_
if(j/weight[0] &= 1)
maxV[0][j] = j/weight[0] * value[0];
printf(&%d&,maxV[N-1][V]);
========================================
完全背包二进制拆分思想
这种实现方式是对完全背包的基本实现做了一个优化，叫“二进制拆分”。所谓“拆分物体”就是将一种无限件物品拆分成有效的几件物品，拆分物体的目的是通过减少物品个数来降低复杂度。
在完全背包中，每种物品i对于容量v来讲实际上相当于有v/c[i]件，故在上述的基本实现中，k就要循环测试v/c[i]次。
这里的拆分是利用了一种二进制思想：即任何数字都可以表示成若干个2^k数字的和，例如7可以用1+2+2^2表示；这很好理解，因为任何正数都可以转成二进制，二进制就是若干个“1”（2的幂数）之和。
所以不管最优策略选择几件物品i，我们都可以将物品i拆成费用为c[i]*2^k，价值为w[i]*2^k的若干件物品。这样物品的状态数就降为了log(v/c[i])，是很大的改进。
在代码实现上，与基本实现的差别很小，区别如下
/* 完全背包 版本2
* Time Complexity
大于O(N*V)
* Space Complexity O(N*V)
* 设 V &= 200 N &= 10
* 状态转移方程：f(i,v) = max{ f(i-1,v-2^k*c[i]) + 2^k*w[i] | 0&=k&=log v/c[i]
* 每件物品降低为 log(v/c[i]) 种状态
for(k = 1; k &= j/weight[i]; k &&= 1)
if(maxV[i-1][j-k*weight[i]] + k*value[i] & max_tmp)
max_tmp = maxV[i-1][j-k*weight[i]] + k*value[i];
对于使用滚动数组的实现，这里就不写了，跟01背包是一样的。
========================================
完全背包中的逆向思维
我们知道，在01背包和完全背包的实现中，都是针对每种物品进行讨论，即外循环都是for i=0…n，然后每种物品对于容量v的变化而求得最大价值；
在完全背包中，由于物品的件数无限，所以我们可以倒过来想，我们针对每个容量讨论，外循环为容量，对于每个容量j，我们求j对于所有物品能装载的最大价值，这样一来我们就能将时间复杂度降为O(N*V)了。代码如下：
#include &iostream&
/* 完全背包 版本3
* Time Complexity
* Space Complexity O(N*V)
* 设 V &= 200 N &= 10
int maxValue[201][11]; /* 记录子问题的各状态 */
int weight[11];
int value[11];
int maxV[201]; /* 记录子问题的最优解 */
void main()
scanf(&%d %d&,&V, &N);
for(i = 0; i & N; ++i)
scanf(&%d %d&,&weight[i],&value[i]);
for(i = 1; i &= V; ++i)
int i_maxV = 0;
/* 记录子问题i的最优解 */
/* 每个容量求面对所有物体能装载的最大价值 */
for(j = 0; j & N; ++j)
if(i &= weight[j])
int tmp = maxV[i-weight[j]] + value[j];
maxValue[i][j] = maxV[i-1] & tmp ? maxV[i-1] :
maxValue[i][j] = maxV[i-1];
if(maxValue[i][j] & i_maxV)
i_maxV = maxValue[i][j];
maxV[i] = i_maxV;
printf(&%d&,maxV[V]);
/* 重定向输出结果到文件 */
freopen(&C:\\dp.txt&,&w&,stdout);
for(i = 0; i &= V; ++i)
for(j = 0; j & N; ++j)
printf(&%d &,maxValue[i][j]);
%d\n&,maxV[i]);
同样，可以将状态转移矩阵重定向输出到文件进行对比，一看就明白了，这里就不贴图片了。
========================================
完全背包使用一维数组
对于01背包和完全背包，无论是空间复杂度还是时间复杂度，最优的方法还是使用一维数组进行实现。
基于01背包的分析，由于不必考虑物品的重复放入，故v的循环采用顺序即可。代码如下：
#include &iostream&
/* 完全背包 版本4
* Time Complexity
* Space Complexity O(V)
* 设 V &= 200 N &= 10
* 状态转移方程：v =0...V; f(v) = max{ f(v), f(v-c[i])+w[i] }
int maxV[201];
/* 记录前i个物品中容量v时的最大价值, 物品可重复 */
int weight[11];
int value[11];
void main()
scanf(&%d %d&,&V, &N);
for(i = 0; i & N; ++i)
scanf(&%d %d&,&weight[i],&value[i]);
for(i = 0; i & N; ++i)
for(j = weight[i]; j &= V; ++j)
/* j&weight[i]的对前面的状态不会有影响 */
int tmp = maxV[j-weight[i]]+value[i];
maxV[j] = (maxV[j] & tmp) ? maxV[j] :
printf(&%d&,maxV[V]);
========================================
PS：值得一提的是，在和完全背包中，我们用到了两种思想，个人认为还是很有用的，其他地方也会用到很多，我们有必要在此留心：
滚动数组压缩空间的思想
二进制拆分的思想
记得有一回看到的面试题就用到了二进制拆分的思想，具体是啥忘了，以后碰到再说吧，就这样。
本文相关代码可以到下载。
（全文完）
参考资料：背包问题九讲
点击鼠标喂喂小老鼠吧
- 38,205 views - 35,830 views - 33,268 views - 32,915 views - 26,302 views - 25,727 views - 25,562 views - 22,898 views - 22,624 views - 20,921 views - 18,252 views - 16,879 views - 16,054 views - 14,776 views - 14,656 views - 14,345 views - 14,049 views - 14,048 views - 13,881 views - 13,286 views - 13,075 views - 12,789 views - 12,755 views - 12,685 views - 12,493 views - 12,256 views - 12,045 views - 11,890 views - 11,492 views - 11,343 views - 11,100 views - 10,751 views - 10,680 views - 10,223 views - 10,215 views - 10,026 views - 9,890 views - 9,888 views - 9,751 views - 9,748 views - 9,139 views - 8,937 views他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)01背包&完全背包&多重背包 - 区别
01背包问题
这是最基本的背包问题，每个物品最多只能放一次
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：&将前i件物品放入容量为v的背包中&这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为&前i-1件物品放入容量为v的背包中&；如果放第i件物品，那么问题就转化为&前i-1件物品放入剩下的容量为v-c[i]的背包中&，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。
过程ZeroOnePack，表示处理一件01背包中的物品，两个参数cost、weight分别表明这件物品的费用和价值。
procedure ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
完全背包问题
第二个基本的背包问题模型，每种物品可以放无限多次
有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(N*V)个状态需要求解，但求解每个状态的时间则不是常数了，求解状态f[i][v]的时间是O(v/c[i])，总的复杂度是超过O(VN)的。
一个简单有效的优化
完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足c[i]&=c[j]且w[i]&=w[j]，则将物品j去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高得j换成物美价廉的i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。
转化为01背包问题求解
O(VN)的算法这个算法使用一维数组，先看伪代码：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]};
你会发现，这个伪代码与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的顺序循环。这就是这个简单的程序为何成立的道理。
这个算法也可以以另外的思路得出。例如，基本思路中的状态转移方程可以等价地变形成这种形式：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]}
多重背包问题
每种物品有一个固定的次数上限
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件&&取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0&=k&=n[i]}
复杂度是O(V*&Sn[i])。
转化为01背包问题
另一种好想好写的基本方法是转化为01背包求解：把第i种物品换成n[i]件01背包中的物品，则得到了物品数为&n[i]的01背包问题，直接求解，复杂度仍然是O(V*&n[i])。
但是我们期望将它转化为01背包问题之后能够像完全背包一样降低复杂度。仍然考虑二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略&&取0..n[i]件&&均能等价于取若干件代换以后的物品。另外，取超过n[i]件的策略必不能出现。
方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1&0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。
分成的这几件物品的系数和为n[i]，表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0..2^k-1和2^k..n[i]两段来分别讨论得出，并不难，希望你自己思考尝试一下。
这样就将第i种物品分成O(log n[i])种物品，将原问题转化为了复杂度为O(V*&log n[i])的01背包问题，是很大的改进。
下面给出O(log amount)时间处理一件多重背包中物品的过程，其中amount表示物品的数量：
procedure MultiplePack(cost,weight,amount)
if cost*amount&=V
CompletePack(cost,weight)
integer k=1
ZeroOnePack(k*cost,k*weight)
amount=amount-k
ZeroOnePack(amount*cost,amount*weight)
这里我们看到了将一个算法的复杂度由O(V*&n[i])改进到O(V*&log n[i])的过程