0-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，。，p6）=（10,5,15,7,6,18,3）。求这一实例的最优解和最大收益。四、 实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、 实验程序 / 贪心法求解#include#includeiomanipusing namespace std;/按照单位物品收益排序，传入参数单位物品收益，物品收益和物品重量的数组，运用冒泡排序void AvgBenefitsSort(float *arry_avgp,float *arry_p,float *arry_w );/获取最优解方法，传入参数为物品收益数组，物品重量数组，最后装载物品最优解的数组和还可以装载物品的重量float GetBestBenifit(float *arry_p,float *arry_w,float *arry_x,float u);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=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 temp=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;/获取最优解方法，传入参数为物品收益数组，物品重量数组，最后装载物品最优解的数组和还可以装载物品的重量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#include#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) 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=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;prin