版权归原作者所有,如有侵权,请联系我们

[科普中国]-背包问题

科学百科
原创
科学百科为用户提供权威科普内容,打造知识科普阵地
收藏
应用

1998年的石溪布鲁克大学算法库的研究表明,在75个算法问题中,背包问题是第18个最受欢迎,第4个最需要解决的问题(前三为后kd树,后缀树和bin包装问题)。3

背包问题出现在各种领域的现实世界的决策过程中,例如寻找最少浪费的方式来削减原材料,4选择投资和投资组合,5选择资产支持资产证券化6,和生成密钥为Merkle-Hellman7和其他背包密码系统。

背包算法的一个早期应用是在测试的构建和评分中,测试者可以选择他们回答哪些问题。对于小例子来说,这是一个相当简单的过程,为测试者提供这样的选择。例如,如果考试包含12个问题,每个问题的价值为10分,测试者只需回答10个问题即可获得100分的最高分。然而,在点值的异质分布的测试 - 即不同的问题值得不同的点值 - 更难以提供选择。 Feuerman和Weiss提出了一个系统,其中学生被给予一个异质测试,共有125个可能的点。学生被要求尽可能回答所有的问题。在总点数加起来为100的问题的可能子集中,背包算法将确定哪个子集给每个学生最高的可能得分。8

定义

我们有n种物品,物品j的重量为wj,价格为pj。

我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。

如果限定每种物品只能选择0个或1个,则问题称为0-1背包问题9。

可以用公式表示为:

最大化

受限于

如果限定物品j最多只能选择bj个,则问题称为有界背包问题。

可以用公式表示为:

最大化

受限于

如果不限定每种物品的数量,则问题称为无界背包问题。

各类复杂的背包问题总可以变换为简单的0-1背包问题进行求解。9

基础背包题目

有N件物品和一个容量为V的背包。第i件物品的重量是w[i],价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。

基本思路

这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。

用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:

f[i][v]=max{ f[i-1][v], f[i-1][v-w[i]]+v[i] }。

可以压缩空间,f[v]=max{f[v],f[v-w[i]]+v[i]}

这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[i-1][v];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-w[i]的背包中”,此时能获得的最大价值就是f [i-1][v-w[i]]再加上通过放入第i件物品获得的价值v[i]。

注意f[v]有意义当且仅当存在一个前i件物品的子集,其费用总和为f[v]。所以按照这个方程递推完毕后,最终的答案并不一定是f[N] [V],而是f[N][0..V]的最大值。如果将状态的定义中的“恰”字去掉,在转移方程中就要再加入一项f[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-w[i]]两个子问题递推而来,能否保证在推f[v]时(也即在第i次主循环中推f[v]时)能够得到f[v]和f[v -w[i]]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-w[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下:

for i=1..N

for v=V..0

f[v]=max{f[v],f[v-w[i]]+v[i]};

其中的f[v]=max{f[v],f[v-w[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]},因为的

f[v-w[i]]就相当于原来的f[i-1][v-w[i]]。如果将v的循环顺序从上面的逆序改成顺序的话,那么则成了f[i][v]由f[i][v-w[i]]推知,与本题意不符,但它却是另一个重要的背包问题P02最简捷的解决方案,故学习只用一维数组解01背包问题是十分必要的。10

示例程序

(完全背包问题求解)

#includeusing namespace std;int findM(int N,int K,int G[],int W[]){    int *M=new int[N+1],i,j,k;         for(i=0;i=0;k++)                       {                          M[j]=M[j]>k*W[i]+M[j-k*G[i]]?M[j]:k*W[i]+M[j-k*G[i]];                           }                   }        }             return M[N];}int main(){        int N,K,i;        while(cin>>N>>K)        {        int *G=new int[K];                int *W=new int[K];                for(i=0;i>G[i]>>W[i];                coutn>>v;for(int i=1;i>c[i]>>w[i];couty then max:=x else max:=y;end;beginreadln(n,m);for i:=1 to n doreadln(c[i],w[i]);for i:=1 to n dofor x:=1 to m doif x>=c[i] then f[i,x]:=max(f[i-1,x-c[i]]+w[i],f[i-1,x])else f[i,x]:=f[i-1,x];writeln(f[n,m]);end.测试数据

//in.txt:

5 100

77 92

22 22

29 87

50 46

99 90

//out.txt

133

//in.txt:

8 200

79 83

58 14

86 54

11 79

28 72

62 52

15 48

68 62

//out.txt

334

C动态规划算法的实现(完整代码)

#include#includetypedefstruct{intobject;intweight;intvalue;}KnapSack;KnapSack*knapsack;//背包数组,用malloc或new动态创建intnum;//物体的个数intcontainer;//背包的最大容量int**array=NULL;//用来存放子问题的结果//动态创建背包voidCreate_KnapSack(){charc;printf("inputthenumberofobjects\n");scanf("%d",&num);knapsack=newKnapSack[num+1];printf("inputweightandvalueof%dobjects,like1:410\n",num);for(inti=1;i