贪婪法求解背包问题

算法设计与分析第五章贪婪法的算法实现代码1、算法1：贪婪法求解背包问题#includeiostreamusingnamespacestd;#definen10#defineM30typedefstruct{floatp;//每个物体的价值floatw;//每个物体的重量floatv;//每个物体的价值重量比}object;voidswap(object&x,object&y){objectt=x;x=y;y=t;}voidbubble(objecta[]){inti,j;for(i=n-1;i0;i--)for(j=0;ji;j++){if(a[j].va[j+1].v)swap(a[j],a[j+1]);}}floatf(objecto[],floatd,floatx[]){inti,j;for(i=0;in;i++){o[i].v=o[i].p/o[i].w;x[i]=0;}floatm=M;bubble(o);for(inti=0;in;i++){cout物体的价值比重是：o[i].v\t;if((i+1)%2==0)coutendl;}for(intj=0;jn;j++){if(o[j].w=m){d=d+o[j].p;m=m-o[j].w;x[j]=1;}else{x[j]=m/o[j].w;d+=x[j]*o[j].p;break;}}returnd;}voidmain(){objecto[n];floata[]={3,4,2,5,7,10,1,6,9,8};floatb[]={7,6,6,8,12,15,4,10,14,13};for(inti=0;in;i++){o[i].w=a[i];o[i].p=b[i];}floatd=0;floatx[n];d=f(o,d,x);cout最优值为：dendl;for(inti=0;in;i++)cout物体的比重为：x[i]=x[i]\n;system(pause);}