背包问题.docx
《背包问题.docx》由会员分享，可在线阅读，更多相关《背包问题.docx（17页珍藏版）》请在冰点文库上搜索。
背包问题
背包问题
01背包
完全背包
多重背包
混合背包
分组的背包问题
有依赖的背包问题
习题
一、01背包问题BACK
问题：
有N件物品和一个容量为V的背包。
第i件物品的费用（即体积，下同）是w[i]，价值是c[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本思路：
这是最基础的背包问题，特点是：
每种物品仅有一件，可以选择放或不放。
用子问题定义状态：
即f[i][v]表示前i件物品（部分或全部）恰放入一个容量为v的背包可以获得的最大价值。
则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}。
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。
所以有必要将它详细解释一下：
“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。
如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-w[i]的背包中”，此时能获得的最大价值就是f[i-1][v-w[i]]再加上通过放入第i件物品获得的价值c[i]。
注意f[i][v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。
所以按照这个方程递推完毕后，最终的答案并不一定是f[N][V]，而是f[N][0..V]的最大值。
如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[i-1][v]，这样就可以保证f[N][V]就是最后的答案。
但是若将所有f[i][j]的初始值都赋为0，你会发现f[n][v]也会是最后的答案。
为什么呢？
因为这样你默认了最开始f[i][j]是有意义的，只是价值为0，就看作是无物品放的背包价值都为0，所以对最终价值无影响，这样初始化后的状态表示就可以把“恰”字去掉。
【优化空间复杂度】
以上方法的时间和空间复杂度均为O（N*V），其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O（V）。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。
那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？
f[i][v]是由f[i-1][v]和f[i-1][v-w[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-w[i]]的值呢？
事实上，这要求在每次主循环中我们以v=V..0的逆序推f[v]，这样才能保证推f[v]时f[v-w[i]]保存的是状态f[i-1][v-w[i]]的值。
♦伪代码如下：
♦ fori=1..N
♦ forv=V..0
♦ f[v]=max{f[v],f[v-w[i]]+c[i]};
♦ 其中f[v]=max{f[v],f[v-w[i]]+c[i]}相当于转移方程f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}，因为现在的f[v-w[i]]就相当于原来的f[i-1][v-w[i]]。
如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-w[i]]推知，与本题意不符，但它却是另一个重要的完全背包问题最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。
【例1】0/1背包
【问题描述】
一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。
【输入格式】
第一行：
两个整数，M（背包容量，M<=200）和N（物品数量，N<=30）；
第2..N+1行：
每行二个整数Wi,Ci，表示每个物品的重量和价值。
【输出格式】
仅一行，一个数，表示最大总价值。
【样例输入】package.in
104
21
33
45
79
【样例输出】package.out
12
【解法一】设f[i][v]表示前i件物品，总重量不超过v的最优价值，则f[i][v]=max（f[i-1][v-w[i]]+c[i]，f[i-1][v]）；f[n][m]即为最优解,给出程序：
#include
usingnamespacestd;
constintmaxm=201,maxn=31;
intm,n;
intw[maxn],c[maxn];
intf[maxn][maxm];
intmax（intx,inty）{x>y?
x:
y;}//求x和y最大值
intmain（）{
scanf（"%d%d",&m,&n）;//背包容量m和物品数量n
for（inti=1;i<=n;i++）//在初始化循环变量部分，定义一个变量并初始化
scanf（"%d%d",&w[i],&c[i]）;//每个物品的重量和价值
for（inti=1;i<=n;i++）//f[i][v]表示前i件物品，总重量不超过v的最优价值
for（intv=m;v>0;v--）
if（w[i]<=v）f[i][v]=max（f[i-1][v],f[i-1][v-w[i]]+c[i]）;
elsef[i][v]=f[i-1][v];
printf（"%d",f[n][m]）;//f[n][m]为最优解
return0;
}
【解法二】本问题的数学模型如下：
设f[v]表示重量不超过v公斤的最大价值，则f[v]=max{f[v]，f[v-w[i]]+c[i]} ，当v>=w[i]，1<=i<=n。
程序如下：
#include
usingnamespacestd;
constintmaxm=2001,maxn=31;
intm,n;
intw[maxn],c[maxn];
intf[maxm];
intmain（）{
scanf（"%d%d",&m,&n）;//背包容量m和物品数量n
for（inti=1;i<=n;i++）
scanf（"%d%d",&w[i],&c[i]）;//每个物品的重量和价值
for（inti=1;i<=n;i++）//设f（v）表示重量不超过v公斤的最大价值
for（intv=m;v>=w[i];v--）
if（f[v-w[i]]+c[i]>f[v]）
f[v]=f[v-w[i]]+c[i];
printf（"%d",f[m]）;//f（m）为最优解
return0;
}
【例2】、完全背包问题BACK
【问题描述】
设有n种物品，每种物品有一个重量及一个价值。
但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于M，而价值的和为最大。
【输入格式】
第一行：
两个整数，M（背包容量，M<=200）和N（物品数量，N<=30）；
第2..N+1行：
每行二个整数Wi,Ci，表示每个物品的重量和价值。
【输出格式】
仅一行，一个数，表示最大总价值。
【样例输入】knapsack.in
104
21
33
45
79
【样例输出】knapsack.out
max=12
【基本思路】
这个问题非常类似于01背包问题，所不同的是每种物品有无限件。
也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。
如果仍然按照解01背包时的思路，令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。
仍然可以按照每种物品不同的策略写出状态转移方程，像这样：
f[i][v]=max{f[i-1][v-k*w[i]]+k*c[i]|0<=k*w[i]<=v}。
将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。
这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。
这个算法使用一维数组，先看伪代码：
fori=1..N
forv=0..V
f[v]=max{f[v],f[v-w[i]]+c[i]};
你会发现，这个伪代码与01背包问题的伪代码只有v的循环次序不同而已。
为什么这样一改就可行呢？
首先想想为什么01背包问题中要按照v=V..0的逆序来循环。
这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-w[i]]递推而来。
换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-w[i]]。
而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-w[i]]，所以就可以并且必须采用v=0..V的顺序循环。
这就是这个简单的程序为何成立的道理。
这个算法也可以以另外的思路得出。
例如，基本思路中的状态转移方程可以等价地变形成这种形式：
f[i][v]=max{f[i-1][v],f[i][v-w[i]]+c[i]}，将这个方程用一维数组实现，便得到了上面的伪代码。
本问题的数学模型如下：
设f（v）表示重量不超过v公斤的最大价值，则f（v）=max{f（v），f（v-w[i]）+c[i]}
（v>=w[i]，1<=i<=n）。
【参考程序】
#include
usingnamespacestd;
constintmaxm=2001,maxn=31;
intn,m,v,i;
intc[maxn],w[maxn];
intf[maxm];
intmain（）
{
scanf（"%d%d",&m,&n）;//背包容量m和物品数量n
for（i=1;i<=n;i++）
scanf（"%d%d",&w[i],&c[i]）;
for（i=1;i<=n;i++）
for（v=w[i];v<=m;v++）//设f[v]表示重量不超过v公斤的最大价值
if（f[v-w[i]]+c[i]>f[v]）f[v]=f[v-w[i]]+c[i];
printf（"max=%d\n",f[m]）;//f[m]为最优解
return0;
}
多重背包问题BACK
有N种物品和一个容量为V的背包。
第i种物品最多有n[i]件可用，每件费用是w[i]，价值是c[i]。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本算法:
这题目和完全背包问题很类似。
基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：
取0件，取1件……取n[i]件。
令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则：
f[i][v]=max{f[i-1][v-k*w[i]]+k*c[i]|0<=k<=n[i]}。
复杂度是O（V*∑n[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的最大整数（注意：
这些系数已经可以组合出1~n[i]内的所有数字）。
例如，如果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（logn[i]）种物品，将原问题转化为了复杂度为O（V*∑logn[i]）的01背包问题，是很大的改进。
【例3】庆功会
【问题描述】
为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。
期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。
【输入格式】
第一行二个数n（n<=500），m（m<=6000），其中n代表希望购买的奖品的种数，m表示拨款金额。
接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和购买的数量（买0件到s件均可），其中v<=100，w<=1000，s<=10。
【输出格式】
第一行：
一个数，表示此次购买能获得的最大的价值（注意！
不是价格）。
【输入样例】
51000
80204
40509
30507
40306
20201
【输出样例】
1040
【解法】进行二进制优化，转换为01背包
【参考程序】
#include
intv[10001],w[10001];
intf[6001];
intn,m,n1;
intmax（inta,intb）{
returna>b?
a:
b;//这句话等于：
if（a>b）returna;elsereturnb;
}
intmain（）{
scanf（"%d%d",&n,&m）;
for（inti=1;i<=n;i++）{
intx,y,s,t=1;
scanf（"%d%d%d",&x,&y,&s）;
while（s>=t）{
v[++n1]=x*t;//相当于n1++;v[n1]=x*t;
w[n1]=y*t;
s-=t;
t*=2;
}
v[++n1]=x*s;
w[n1]=y*s;//把s以2的指数分堆：
1，2，4，…，2^（k-1），s-2^k+1,
}
for（inti=1;i<=n1;i++）
for（intj=m;j>=v[i];j--）
f[j]=max（f[j],f[j-v[i]]+w[i]）;
printf（"%d\n",f[m]）;
return0;
}
【例4】混合背包BACK
【问题描述】
一个旅行者有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。
有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
【输入格式】
第一行：
二个整数，V（背包容量，V<=200），N（物品数量，N<=30）；
第2..N+1行：
每行三个整数Wi,Ci,Pi，前两个整数分别表示每个物品的重量，价值，第三个整数若为0，则说明此物品可以购买无数件，若为其他数字，则为此物品可购买的最多件数（Pi）。
【输出格式】
仅一行，一个数，表示最大总价值。
【样例输入】mix.in
104
210
331
454
【样例输出】mix.out
11
【参考程序】
#include
usingnamespacestd;
intm,n;
intw[31],c[31],p[31];
intf[201];
intmax（intx,inty）{returnx>y?
x:
y;}
intmain（）{
scanf（"%d%d",&m,&n）;
for（inti=1;i<=n;i++）
scanf（"%d%d%d",&w[i],&c[i],&p[i]）;
for（inti=1;i<=n;i++）
if（p[i]==0）{//完全背包
for（intj=w[i];j<=m;j++）
f[j]=max（f[j],f[j-w[i]]+c[i]）;
}
else{
for（intj=1;j<=p[i];j++）//01背包和多重背包
for（intk=m;k>=w[i];k--）
f[k]=max（f[k],f[k-w[i]]+c[i]）;
}
printf（"%d",f[m]）;
return0;
}
【分组的背包问题】BACK
问题
有N件物品和一个容量为V的背包。
第i件物品的费用是w[i]，价值是c[i]。
这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
算法
这个问题变成了每组物品有若干种策略：
是选择本组的某一件，还是一件都不选。
也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有f[k][v]=max{f[k-1][v]，f[k-1][v-w[i]]+c[i]|物品i属于第k组}。
使用一维数组的伪代码如下：
for所有的组k
forv=V..0
for所有的i属于组k
f[v]=max{f[v],f[v-w[i]]+c[i]}
注意这里的三层循环的顺序，“forv=V..0”这一层循环必须在“for所有的i属于组k”之外。
这样才能保证每一组内的物品最多只有一个会被添加到背包中。
另外，显然可以对每组中的物品应用完全背包中“一个简单有效的优化”。
【例6】分组背包
【问题描述】
一个旅行者有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。
这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
【输入格式】
第一行：
三个整数，V（背包容量，V<=200），N（物品数量，N<=30）和T（最大组号，T<=10）；
第2..N+1行：
每行三个整数Wi,Ci,P，表示每个物品的重量，价值，所属组号。
【输出格式】
仅一行，一个数，表示最大总价值。
【样例输入】group.in
1063
211
331
482
692
283
393
【样例输出】group.out
20
【参考程序】
#include
usingnamespacestd;
intv,n,t;
intw[31],c[31];
inta[11][32],f[201];
intmain（）{
scanf（"%d%d%d",&v,&n,&t）;
for（inti=1;i<=n;i++）{
intp;
scanf（"%d%d%d",&w[i],&c[i],&p）;
a[p][++a[p][0]]=i;
}
for（intk=1;k<=t;k++）
for（intj=v;j>=0;j--）
for（inti=1;i<=a[k][0];i++）
if（j>=w[a[k][i]]）{
inttmp=a[k][i];
if（f[j]f[j]=f[j-w[tmp]]+c[tmp];
}
printf（"%d",f[v]）;
return0;
}
【有依赖的背包问题】BACK
简化的问题
这种背包问题的物品间存在某种“依赖”的关系。
也就是说，i依赖于j，表示若选物品i，则必须选物品j。
为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。
算法
这个问题由NOIP2006金明的预算方案一题扩展而来。
遵从该题的提法，将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。
由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成。
按照背包问题的一般思路，仅考虑一个主件和它的附件集合。
可是，可用的策略非常多，包括：
一个也不选，仅选择主件，选择主件后再选择一个附件，选择主件后再选择两个附件……无法用状态转移方程来表示如此多的策略。
（事实上，设有n个附件，则策略有2^n+1个，为指数级。
）
考虑到所有这些策略都是互斥的（也就是说，你只能选择一种策略），所以一个主件和它的附件集合实际上对应于分组的背包中的一个物品组，每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是这个策略中的物品的值的和。
但仅仅是这一步转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多。
再考虑分组的背包中的一句话：
可以对每组中的物品应用完全背包中“一个简单有效的优化”。
这提示我们，对于一个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。
所以，我们可以对主件i的“附件集合”先进行一次01背包，得到费用依次为0..V-w[i]所有这些值时相应的最大价值f'[0..V-w[i]]。
那么这个主件及它的附件集合相当于V-w[i]+1个物品的物品组，其中费用为w[i]+k的物品的价值为f'[k]+c[i]。
也就是说原来指数级的策略中有很多策略都是冗余的，通过一次01背包后，将主件i转化为V-w[i]+1个物品的物品组，就可以直接应用分组的背包的算法解决问题了。
更一般的问题是：
依赖关系以图论中“森林”的形式给出（森林即多叉树的集合），也就是说，主件的附件仍然可以具有自己的附件集合，限制只是每个物品最多只依赖于一个物品（只有一个主件）且不出现循环依赖。
解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。
唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的01背包中的物品了。
若这个附件也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。
事实上，这是一种树形DP，其特点是每个父节点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。
这已经触及到了“泛化物品”的思想。
看完P08后，你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品
升级会员 