背包算法问题

1、背包问题贪心方法实验日志实验题目：1)求以下情况背包问题的最优解：n=7, M=15 ( Pi, , p7) = (10, 5, 15, 7, 6, 18, 3)和(W1, ,w)=( 2, 3, 5, 7, 1, 4, 1)。实验目的：1. 掌握贪心方法算法思想；2. 熟练使用贪心算法之背包问题解决相应的问题。实验思想：贪心方法是一种改进了的分级处理方法。它首先根据题意，选取一种量度标准。然后按这种量度标准对这 n个输入排序，并按排序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此解输入加到这部分解中。这种能够得到某种度量意义下的最优解

2、的分级处理方法称为 贪心方法。1.背包问题(1)背包问题的描述：已知有n种物品和一个可容纳 M重量的背包，每种物品 i的重量为Wi。假定将物品i的一部分Xi放入背包就会得到 PiXi的效益，这 里，0 Xi 1, Pi 0。显然，由于背包容量是M因此，要求所有选中要装入背包的物品总重量不得超过M.。如果这n件物品的总重量不超过则把所有物品装入背包自然获得最大效益。现需解决的问题是， 这些物品重量的和大于 M该如何装包。由以上叙述，可将这个问题形式表述如下：极大化PiXi1 i n约束条件WjXj M1 i n0Xi1, Pi0, Wi0,1in(2)用贪心策略求解背包问题首先需选出最优的量度标

3、准。不妨先取目标函数作为量度标准，即每装的物品放不进去， 则可只取其一部分来装满背包。 但这最后一次的方法可能 不符合使背包每次获得最大效益增量的量度标准， 这可以换一种能获得最大 增量的物品，将它(或它的一部分)放入背包，从而使最后一次装包也符合 量度标准的要求。算法如下所示。算法 2 1背包问题的贪心算法procedure GREEDY-KNAPSACK(P,W,M,X,n)P (1: n)禾口 W( 1: n)分别含有按 P (i ) /W( i) P (i+1 ) / W (i+1 ) 排序的n件物品的效益值和重量。M是背包的容量大笑，而X (1： n)是解向量。 /real P(1：

4、 n) ， W( 1 ： n) ,X ( 1 ： n)， M， cu；integer i ， n;X 0 / 将解向量初始化为零cu M /cu 是背包剩余容量for i 1 to n doif W(i)cu then exit endifX(i)1cu cu-W(i)repeatif i n then X(i)cu/W(i)endifend GREEDY-KNAPSACK实验代码：#includeusing namespace std;void beibao(double *w,double *v,double *x,double n,double *C)int i,j,temp;for(i

5、=0;in-1;i+)for(j=i+1;jn;j+)if(vi/wivj/wj)temp=vi;vi=vj; vj=temp; temp=wi; wi=wj; wj=temp; for(i=0;in;i+) xi=0;for(i=0;*C!=0;i+)if(wi*C)xi=wi;*C=*C-wi;elsexi=*C;*C=*C-*C;void main()int i;double *w,*v,n,C;double *x;cout 请输入物品数 n;w=new double(n);/ 动态分配内存 v=new double(n);x=new double(n);cout 请输入背包的容量 C;:endl;:endl;cout 请分别输入 n 个物品的重量 for(i=0;iwi;cout 请分别输入 n 个物品的价值 for(i=0;ivi;beibao(w,v,x,n,&C);cout 装入的物品为 :endl; for(i=0;in;i+)if(xi!