《背包问题-贪心法和动态规划法求解》由会员分享，可在线阅读，更多相关《背包问题-贪心法和动态规划法求解（6页珍藏版）》请在金锄头文库上搜索。
1、实验四“0-1”背包问题一、一、实验目的与要求实验目的与要求熟悉 C/C+语言的集成开发环境；通过本实验加深对贪心算法、动态规划算法的理解。二、二、实验内容实验内容: :掌握贪心算法、动态规划算法的概念和基本思想，分析并掌握“0-1”背包问题的求解方法，并分析其优缺点。三、三、实验题实验题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，
2、 。 。 。 ，p6）=（10,5,15,7,6,18,3） 。求这一实例的最优解和最大收益。四、四、实验步骤实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、五、实验程序实验程序/贪心法求解#include#includeiomanipusing namespace std;/按照单位物品收益排序， 传入参数单位物品收益， 物品收益和物品重量的数组，运用冒泡排序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()float w7=2,3,5,7,1,4,1;/物品重量数组float p7=10,5,15,7,6,18,3;/物品收益数组float avgp7=0;/单位毒品的收益数组float x7=0;/最后装载物品的最优解数组const float M=15;/背包所能的载重float ben=0;/最后的收益AvgBenefitsSort(avgp,p,w);ben
4、=GetBestBenifit(p,w,x,M);coutendlbenendl;/输出最后的收益system(pause);return 0;/按照单位物品收益排序， 传入参数单位物品收益， 物品收益和物品重量的数组，运用冒泡排序void AvgBenefitsSort(float *arry_avgp,float *arry_p,float *arry_w )/求出物品的单位收益for(int i=0;i7;i+)arry_avgpi=arry_pi/arry_wi;coutendl;/把求出的单位收益排序，冒泡排序法 int exchange=7;int bound=0;float te
5、mp=0;while(exchange)bound=exchange;exchange=0;for(int i=0;ibound;i+)if(arry_avgpiarry_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;arry_wi=arry_wi+1;arry_wi+1=temp; exchange=i;/获取最优解方法，传入参数为物品收益数组
6、，物品重量数组，最后装载物品最优解的数组和还可以装载物品的重量float GetBestBenifit(float *arry_p,float *arry_w,float *arry_x,float u)int i=0;/循环变量ifloat benifit=0;/最后收益while(i0)arry_xi=arry_wi;/把当前物品重量缴入最优解数组 benifit+=arry_pi;/收益增加当前物品收益 u-=arry_wi;/背包还能载重量减去当前物品重量coutarry_xi ;/输出最优解i+;return benifit;/返回最后收益/动态规划法求解#include#inclu
7、de#define n 6void DKNAP(int 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:);scanf(%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(int p,int w,int M,const int m)
8、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(i=1;in;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&w2kww)p2next=p2k;w2next=w2k;next+;k+;if(k=h&w2k=ww)if(ppp2next-1)p2next=pp;w2next
9、=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;i0;i-)next=Fi;next-;pp=pk=p2next;ww=w2next;while(ww+wiM&nextFi-1)next=next-1;pp=p2next;ww=w2next;if(ww+wiFi-1)px=pp+pi;if(pxpk&ww+wi=M)si=1;M=M-wi;printf(M=%d ,M);else si=0;for(i=1;i=n;i+)printf(%2d ,si);六、六、实验结果实验结果1 1、贪心法截图：、贪心法截图：七、七、实验分析实验分析
