背包问题-贪心法和动态规划法求解

1、v1.0可编辑可修改实验四 “0-1”背包问题1、 实验目的与要求熟悉C/C+语言的集成开发环境；通过本实验加深对贪心算法、动态规划算法的理解。2、 实验内容：掌握贪心算法、动态规划算法的概念和基本思想，分析并掌握“0-1 ”背包问题的求解方法，并分析其优缺点。3、 实验题1. “0-1 ”背包问题的贪心算法2. “0-1 ”背包问题的动态规划算法说明：背包实例采用教材 P132习题六的6-1中的描述。要求每种的算法都给出最大收 益和最优解。设有背包问题实例 n=7, M=15, (w0,w1,。w6)= (2,3,5,7,1,4,1),物品装入背包的收益为：(p0, p1,。，p6) = (

2、10,5,15,7,6,18,3)。求这一实例的最优解和最大收益。4、 实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。5、 实验程序/贪心法求解#include <iostream>#include "iomanip"using namespacestd;/按照单位物品收益排序，传入参数单位物品收益，物品收益和物品重量的数组，运用冒泡排序void AvgBenefitsSort( float *arry_avgp, float *arry_p, float *arry_w );/获取最优解方法，

3、传入参数为物品收益数组，物品重量数组，最后装载物品最优解的数组和还可以装载物品的重量float GetBestBenifit( float *arry_p, float *arry_w, float *arry_x, floatu)；int main()floatw7=2,3,5,7,1,4,1;/物品重量数组floatp7=10,5,15,7,6,18,3;/物品收益数组floatavgp7=0;/单位毒品的收益数组floatx7=0；/最后装载物品的最优解数组constfloat M=15;/背包所能的载重floatben=0;/最后的收益AvgBene巾tsSort(avgp,p,w);

4、ben=GetBestBenifit(p,w,x,M);cout<<endl<<ben<<endl;/ 输出最后的收益system( "pause");return 0;/按照单位物品收益排序，传入参数单位物品收益，物品收益和物品重量的数组,运用冒泡排序void AvgBenefitsSort( float *arry_avgp, float *arry_p, float *arry_w )/求出物品的单位收益for (int i=0;i<7;i+)arry_avgpi=arry_pi/arry_wi;cout<<end

5、l;/把求出的单位收益排序，冒泡排序法int exchange=7;int bound=0;float temp=0;while (exchange)bound=exchange;exchange=0;for (int i=0;i<bound;i+)if (arry_avgpi<arry_avgpi+1)/交换单位收益数组temp=arry_avgpi;arry_avgpi=arry_avgpi+1;arry_avgpi+1=temp;/交换收益数组temp=arry_pi;arry_pi=arry_pi+1;/arry_pi+1=temp;交换重量数组temp=arry_wi;a

6、rry_wi=arry_wi+1;arry_wi+1=temp;exchange=i;/获取最优解方法，传入参数为物品收益数组，物品重量数组，最后装载物品最优解的数组和还可以装载物品的重量float GetBestBenifit( floatint i=0;float benifit=0;while (i<7)if (u-arry_wi>0)arry_xi=arry_wi;benifit+=arry_pi;u-=arry_wi;cout<<arry_xi<<i+；*arry_p, float *arry_w, float *arry_x, float u)/

7、循环变量i/最后收益/把当前物品重量缴入最优解数组/收益增加当前物品收益/背包还能载重量减去当前物品重量/输出最优解/返回最后收益return benifit;/动态规划法求解#include <>#include <>#define n 6void DKNAP(nt p口， int w口，int M, const int m);void main()int pn+1,wn+1;int M,i,j;int m=1;for (i=1;i<=n;i+)m=m*2;printf( "nin put the weight and the p:");sc

8、anf( "%d %d",&wi,&pi);printf( "%d",m);printf( "n in put the max weight M:");scanf( "%d",&M);DKNAP(p,w,M,m);void DKNAP(nt p口， int w口，int M, const int m)int p2m,w2m,pp,ww,px;int Fn+1,pk,q,k,l,h,u,i,j,next,max,sn+1;F0=1;p21=w21=0;l=h=1;F1=next=2;for (

9、i=1;i<n;i+)(k=l;max=0;u=l;for (q=l;q<=h;q+)if (w2q+wi<=M)&&max<=w2q+wi)(u=q;max=w2q+wi;for (j=l;j<=u;j+)(pp=p2j+pi;ww=w2j+wi;while (k<=h&&w2k<ww)(p2next=p2k;w2next=w2k;next+;k+;if (k<=h&&w2k=ww)if (pp<=p2k)pp=p2k;k+;)else if (pp>p2next-1)(p2next=

10、pp;w2next=ww;next+;)while (k<=h&&p2k<=p2next-1) k+;)while (k<=h)(p2next=p2k;w2next=w2k;next=next+1;k+;)l=h+1;h=next-1;Fi+1=next;)for (i=1;i<next;i+)printf( "%2d%2d ",p2i,w2i);for (i=n;i>0;i-)next=Fi;next-;pp=pk=p2next;ww=w2next;while (ww+wi>M&&next>Fi-1)next=next-1;pp=p2next;ww=w2next;if (ww+wi<=M&&next>Fi-1) px=pp+pi;if (px>pk