贪婪法求解背包问题.docx

《 贪婪法求解背包问题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验二贪婪法一、实验目的1)理解和掌握贪婪算法的基本思想；2)使用贪婪算法求解背包问题以及最小花费生成树问题。二、方法原理贪心算法就是做出一系列选择，使原问题达到最优解。在每一个决策点，都是做出当前看来的最优选择。三、实验设备PC机一台，C语言、PASCAL语言、Matlab任选四、方法原理贪心算法就是做出一系列选择，使原问题达到最优解。在每一个决策点，都是做出当前看来的最优选择。五、实验内容1)利用贪婪法求如下背包问题的最优解：n=5,M=100,价值P={20,30,66,40,60}，重量为w={10,20,30,40,50}

2、。六、实验要求1)认真分析题目的条件和要求，复习相关的理论知识，选择适当的解决方案和算法；2)编写上机实验程序，作好上机前的准备工作；3)上机调试程序，并试算各种方案，记录计算的结果（包括必要的中间结果）；4)分析和解释计算结果；5)按照要求书写实验报告；源代码：#include#include#includeusingnamespacestd;#definen5#defineM100typedefstruct{ints;floatp;//价值floatw;floatt;//

3、价值重量比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].t>z){i+=1;if(i!=k)swap(obj[i],obj[k]);}}swap(obj[low],obj[i]);returni;}voi

4、dquick_sort(OBJECTobj[],intlow,inthigh){intk;if(lowobj[j+1].s)swap(obj[j],obj[j+1]

5、);}}}floatknapsack_greedy(OBJECTobj[]){inti;floatm,r=0;for(i=0;i

6、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;i

7、j);sort_recover(obj);for(i=0;i