背包算法问题.doc

《背包算法问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、每装入一件物品就使背包获得最大可能的效益值增量。在这种量度标准下的贪心方法就是按效益值的非增次序将物品一件件放到背包中去。如果正在考虑中的物品放不进去，则可只取其一部分来装满背包。但这最后一次的方法可能不符合使背包每次获得最大效益增量的量度标准，这可以换一种能获得最大增量的物品，将它（或它的一部分）放入背包，从而使最后一次装包也符合量度标准的要求。算法如下所示。算法2．1背包问题的贪心算法procedureGREEDY-KNAPSACK(P,W,M,X,n)//P（1：n）和W（1：n）分别含有按P（i）/W（i）≥P

4、（i+1）/W（i+1）排序的n件物品的效益值和重量。M是背包的容量大笑，而X（1：n）是解向量。//realP(1：n)，W（1：n）,X（1：n），M，cu；integeri，n;X0//将解向量初始化为零cuM//cu是背包剩余容量fori1tondoifW(i)>cuthenexitendifX(i)1cucu-W(i)repeatifi≤nthenX(i)cu/W(i)endifendGREEDY-KNAPSACK实验代码：#includeusingnamespacestd;voidbei

5、bao(double*w,double*v,double*x,doublen,double*C){inti,j,temp;for(i=0;i

6、{x[i]=*C;*C=*C-*C;}}}voidmain(){inti;double*w,*v,n,C;double*x;cout<<"请输入物品数"<>n;w=newdouble(n);//动态分配内存v=newdouble(n);x=newdouble(n);cout<<"请输入背包的容量"<>C;cout<<"请分别输入"<>w[i];cout<<"请分别输入"<

7、endl;for(i=0;i>v[i];beibao(w,v,x,n,&C);cout<<"装入的物品为:"<