分类： C/C++
2011-11-26 18:00:10
背包问题(Knapsack problem)是一种组合优化的问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。 相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。
也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？
背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？如右图：
我们有n种物品，物品j的重量为wj，价格为pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。
如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。可以用公式表示为：
maximize
subject to
如果限定物品j最多只能选择bj个，则问题称为有界背包问题。可以用公式表示为：
maximize
subject to
如果不限定每种物品的数量，则问题称为无界背包问题。
如果重量w1, …, wn和W都是非负的，那么用，可以用解决背包问题。下面描述了无界背包问题的解法。
简便起见，我们假定重量都是正的（wj > 0）。在总重量不超过W的前提下，我们希望总价格最高。对于Y ≤ W，我们将在总重量不超过Y的前提下，总价格所能达到的最高值定义为A(Y)。A(W)即为问题的答案。
显然，A(Y)满足：
A(0) = 0
A(Y) = max { A(Y - 1), max { pj + A(Y - wj) | wj≤ Y } }
其中，pj为第j种物品的价格。
关于第二个公式的一个解释：总重量为Y时背包的最高价值可能有两种情况，第一种是该重量无法被完全填满，这对应于表达式A(Y - 1)。第二种是刚好填满，这对应于一个包含一系列刚好填满的可能性的集合，其中的可能性是指当最后放进包中的物品恰好是重量为wj的物品时背包填满并达到最高价值。而这时的背包价值等于重量为wj物品的价值和当没有放入该物品时背包的最高价值之和。故归纳为表达式pj + A(Y - wj)。最后把所有上述情况中背包价值的最大值求出就得到了A(Y)的值。
如果总重量为0，总价值也为0。然后依次计算A(0), A(1), …, A(W)，并把每一步骤的结果存入表中供后续步骤使用，完成这些步骤后A(W)即为最终结果。由于每次计算A(Y)都需要检查n种物品，并且需要计算W个A(Y)值，因此动态规划解法的为O(nW)。如果把w1, …, wn, W都除以它们的，算法的时间将得到很大的提升。
尽管背包问题的时间复杂度为O(nW)，但它仍然是一个问题。这是因为W同问题的输入大小并不成线性关系。原因在于问题的输入大小仅仅取决于表达输入所需的比特数。事实上，log W，即表达W所需的比特数，同问题的输入长度成线性关系。
类似的方法可以解决0-1背包问题，算法同样需要伪多项式时间。我们同样假定w1, …, wn和W都是正数。我们将在总重量不超过Y的前提下，前j种物品的总价格所能达到的最高值定义为A(j, Y)。
A(j, Y)的递推关系为：
A(0, Y) = 0
A(j, 0) = 0
如果wj > Y, A(j, Y) = A(j - 1, Y)
如果wj ≤ Y, A(j, Y) = max { A(j - 1, Y), pj + A(j - 1, Y - wj) }
通过计算A(n, W)即得到最终结果。为提高算法性能，我们把先前计算的结果存入表中。因此算法需要的时间和空间都为O(nW)，通过对算法的改进，空间的消耗可以降至O(W)。
推广的背包问题有二次背包问题，多维背包问题，多目标背包问题等。
二次背包问题是背包问题的一种推广形式:
maximize
subject to
for all
有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]。
注意f[i][v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是f[N][V]，而是f[N][0..V]的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[i][v-1]，这样就可以保证f[N][V]就是最后的答案。至于为什么这样就可以，由你自己来体会了。
优化空间复杂度以上方法的时间和空间复杂度均为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-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：
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]]推知，与本题意不符，但它却是另一个重要的背包问题最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。
总结01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。
动态规划——0/1背包问题 收藏
动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。
比如01背包问题。
因为背包最大重量M未知。所以，我们的程序要从1到M一个一个的试。比如，开始任选N件物品的一个。看对应M的背包，能不能放进去，如果能放进去，并且还有多的空间，则，多出来的空间里能放N-1物品中的最大价值。怎么能保证总选择是最大价值呢？看下表。
测试数据：
10,3
3,4
4,5
5,6
c[i][j]数组保存了1,2,3号物品依次选择后的最大价值.
这个最大价值是怎么得来的呢?从背包重量为0开始,1号物品先试,0,1,2,的重量都不能放.所以置0,背包重量为3则里面放4.这样,这一排背包重量为4,5,6,....10的时候，最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包重量为3的时候，最佳方案还是上一排的最价方案c为4.而背包重量为5的时候，则最佳方案为自己的重量5.背包重量为7的时候，很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排
c3的最佳方案是4.所以。总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包重量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)
从以上最大价值的构造过程中可以看出。
f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.这回清楚了吗?
按照《计算机算法设计与分析》中所讲到的，按照动态规划的解题方法，步骤如下：
1，分析问题
由于对于一个物件序列a1~an，每个的选择的可能只能是0或1，于是问题就转化为寻找一个0/1整数序列x1~xn，xi=0或xi=1。
2，寻找最优子结构。
假设,x1~xi是在物件序列a1~ai中选择的一个最优选择序列，那么，x1~x(i-1)一定是从物件序列a1~a(i-1)选择的最有选择序列。
但是，需要注意的是，物件序列a1~a(i-1)和a1~ai在进行选择时，它们的限制条件不一样，即要求的最大重量限制不同。所以不能简单的按照一般的子问题来考虑（即，设c[i]为从a1~ai中最优选择的最大价值，那么c[i]=c[i-1]+vi，这样没有考虑到最大重量限制）。
当考虑到最大重量限制时，设c[i][j]为“从物件序列a1~ai中选择一个整数序列x1~xi，且使总重量不超过j时的最大总价值”。
重新考虑最优子结构：x1~x(i-1)为从物件序列a1~a(i-1)中选择的最优整数序列，并且保证：
（1）当若xi=1，即选择了物件ai，则需保证总重量不超过j-wi。
（2）当若xi=0，即不选择ai，则需保证总重量不超过j。
于是，c[i][j] =
(j>=ai时)
max(c[i-1][j]), //不选择ai
c[i-1][j-wi]+vi) //选择ai
(j
下面是实际程序:
#include
int c[10][100];
int knapsack(int m,int n)
{
int i,j,w[10],p[10];
for(i=1;i
for(i=0;i<10;i++)
for(j=0;j<100;j++)
c[i][j]=0;
for(i=1;i
if(w[i]<=j)
{
if(p[i]+c[i-1][j-w[i]]>c[i-1][j])
c[i][j]=p[i]+c[i-1][j-w[i]];
else
c[i][j]=c[i-1][j];
}
else c[i][j]=c[i-1][j];
}
return(c[n][m]);
}
int main()
{
int m,n;int i,j;
scanf("%d,%d",&m,&n);
printf("Input each one:\n");
printf("%d",knapsack(m,n));
printf("\n");
for(i=0;i<10;i++)
for(j=0;j<15;j++)
{
printf("%d ",c[i][j]);
if(j==14)printf("\n");
}
system("pause");
}
