贪婪法求解背包问题

实验二贪婪法一、实验目的1)理解和掌握贪婪算法的基本思想；2)使用贪婪算法求解背包问题以及最小花费生成树问题。二、方法原理贪心算法就是做出一系列选择，使原问题达到最优解。在每一个决策点，都是做出当前看来的最优选择。三、实验设备PC机一台，C语言、PASCAL语言、Matlab任选四、方法原理贪心算法就是做出一系列选择，使原问题达到最优解。在每一个决策点，都是做出当前看来的最优选择。五、实验内容1)利用贪婪法求如下背包问题的最优解：n=5,M=100,价值P={20,30,66,40,60}，重量为w={10,20,30,40,50}。六、实验要求1)认真分析题目的条件和要求，复习相关的理论知识，选择适当的解决方案和算法；2)编写上机实验程序，作好上机前的准备工作；3)上机调试程序，并试算各种方案，记录计算的结果（包括必要的中间结果）；4)分析和解释计算结果；5)按照要求书写实验报告；源代码：#includestdio.h#includestdlib.h#includeiostreamusingnamespacestd;#definen5#defineM100typedefstruct{ints;floatp;//价值floatw;floatt;//价值重量比floatx;}OBJECT;OBJECTobj[n];voidswap(float&x,float&y){floatt;t=x;x=y;y=t;}floatdivide_and_conquer(OBJECTobj[],intlow,inthigh){intk,i=low;floatz=obj[low].t;for(k=low+1;k=high;k++){if(obj[k].tz){i+=1;if(i!=k)swap(obj[i],obj[k]);}}swap(obj[low],obj[i]);returni;}voidquick_sort(OBJECTobj[],intlow,inthigh){intk;if(lowhigh){k=divide_and_conquer(obj,low,high);quick_sort(obj,low,k-1);quick_sort(obj,k+1,high);}}voidsort_recover(OBJECTobj[]){inti,j,temp;for(i=0;in-1;i++){for(j=0;jn-1-i;j++){if(obj[j].sobj[j+1].s)swap(obj[j],obj[j+1]);}}}floatknapsack_greedy(OBJECTobj[]){inti;floatm,r=0;for(i=0;in;i++){obj[i].t=obj[i].p/obj[i].w;obj[i].x=0;}quick_sort(obj,0,4);m=M;printf(物体价值重量价值重量比结果\n);printf(=========================================\n);for(i=0;in;i++){if(obj[i].w=m){obj[i].x=1;m-=obj[i].w;r+=obj[i].p;}else{obj[i].x=m/obj[i].w;r+=obj[i].x*obj[i].p;break;}}returnr;}voidmain(){inti;floatr;//floatx[]={0};floats[]={1,2,3,4,5};floatp[]={20,30,66,40,60};floatw[]={10,20,30,40,50};for(i=0;in;i++){obj[i].s=s[i];obj[i].p=p[i];obj[i].w=w[i];}r=knapsack_greedy(obj);sort_recover(obj);for(i=0;in;i++){printf(%d%2.0f%2.0f%2.1f%1.1f\n,obj[i].s,obj[i].p,obj[i].w,obj[i].t,obj[i].x);}printf(\n最大价值为：%f\n,r);printf(背包问题的解向量：X={);for(i=0;in;i++){printf(%1.1f,obj[i].x);if(i4)printf(,);}printf(});system(pause);}结果：