动态规划

第九章动态规划第三节背包问题第三节背包问题一、01背包问题问题：有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]即为最优解,给出程序：#includecstdiousingnamespacestd;constintmaxm=201,maxn=31;intm,n;intw[maxn],c[maxn];intf[maxn][maxm];intmax(intx,inty){xy?x:y;}//求x和y最大值intmain(){scanf(%d%d,&m,&n);//背包容量m和物品数量nfor(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;v0;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;}使用二维数组存储各子问题时方便，但当maxm较大时，如maxm=2000时不能定义二维数组f，怎么办，其实可以用一维数组。【解法二】本问题的数学模型如下：设f[v]表示重量不超过v公斤的最大价值，则f[v]=max{f[v]，f[v-w[i]]+c[i]}，当v=w[i]，1=i=n。程序如下：#includecstdiousingnamespacestd;constintmaxm=2001,maxn=31;intm,n;intw[maxn],c[maxn];intf[maxm];intmain(){scanf(%d%d,&m,&n);//背包容量m和物品数量nfor(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;}总结:01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。二、完全背包问题问题:有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。基本思路:这个问题非常类似于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..Nforv=0..Vf[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]}，将这个方程用一维数组实现，便得到了上面的伪代码。【例9-12】、完全背包问题【问题描述】设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。【输入格式】第一行：两个整数，M(背包容量，M=200)和N(物品数量，N=30)；第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。【输出格式】仅一行，一个数，表示最大总价值。【样例输入】knapsack.in10421334579【样例输出】knapsack.outmax=12【解法一】设f[i][v]表示前i件物品，总重量不超过v的最优价值，则f[i][v]=max(f[i][v-w[i]]+c[i]，f[i-1][v])；f[n][m]即为最优解。【参考程序】#includecstdiousingnamespacestd;constintmaxm=201,maxn=31;intm,n;intw[maxn],c[maxn];intf[maxn][maxm];intmain(){scanf(%d%d,&m,&n);//背包容量m和物品数量nfor(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=1;v=m;v++)if(vw[i])f[i][v]=f[i-1][v];elseif(f[i-1][v]f[i][v-w[i]]+c[i])f[i][v]=f[i-1][v];elsef[i][v]=f[i][v-w[i]]+c[i];printf(max=%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）。【参考程序】#includecstdiousingnamespacestd;constintmaxm=2001,maxn=31;intn,m,v,i;intc[maxn],w[maxn];intf[maxm];intmain(){scanf(%d%d,&m,&n);//背包容量m和物品数量nfor(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;}一个简单有效的优化完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足w[i]=w[j]且c[i]=c[j]，则将物品j去掉，不用考虑。这个优化的正确性显然：任何情况