贪心算法解决0-1背包问题.doc

《贪心算法解决0-1背包问题.doc》由会员分享，可在线阅读，更多相关《贪心算法解决0-1背包问题.doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品文档，仅供学习与交流，如有侵权请联系网站删除 贪心算法-0-1背包问题1、问题的描述有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,4,2,1,3，它们的价值分别是3,5,6,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？贪心算法的思想：贪心原则为单位价值最大且重量最小，不超过背包最大承重量为约束条件。也就是说，存在单位重量价值相等的两个包，则选取重量较小的那个背包。2、代码及注释#include #define M 5/定义一个node结构体，用来存放物体的重量和价值struct node float value;/价值 float weig

2、ht;/重量 int flag; /用来判别这个物体是否装进背包NodeM,temp;float Value,curvalue=0;/总价值和当前价值float Weight,curweight=0;/背包的最大承受重量和现有重量/按性价比排序void sort() int i,j; /遍历所有物品 for(i=0;iM-1;i+) /与之后的物品进行比较 for(j=i+1;jM;j+) /判断性价比较最高性价比 if(Nodei.value/(float)Nodei.weight)Nodej.value/(float)Nodej.weight) /进行交换 temp=Nodei; Node

3、i=Nodej; Nodej=temp;/装载主要方法void load() int i;/遍历所有物品 for(i=0;iM;i+)/判断加入物品否是否大于背包所能承载的最大重量 if(Nodei.weight+curweight)=Weight) curvalue+=Nodei.value; curweight+=Nodei.weight; Nodei.flag=1;/进行标记 else /进行标记 Nodei.flag=0;/进行结果的输出void putout() int i; printf(选中物品的重量分别为：); for(i=0;iM;i+) if(Nodei.flag) pri

4、ntf(%.2f ,Nodei.weight); printf(n总价值为:%.2f,curvalue);int main() int i; printf(请输入物品的重量和价值：n); for(i=0;iM;i+) printf(请输入第%d个物品的重量和价值,i+1); scanf(%f%f,&Nodei.weight,&Nodei.value); printf(n请输入背包容积：); scanf(%f,&Weight); sort(); load(); putout(); return 0;3、 运行结果 (1)在某种情况下可以通过局部最优选择达到整体最优。(2) 贪心算法并不能使所有符

5、合局部最优的选择使得整体达到最优4、运行结果 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。 在这个程序中，采用性价比的方式来做出当前最好的选择，然后再不大于背包所能承载的最大重量的时候将他标记成1，否则标记成0. 最后在输出的时候选择标记为1 的输出，用来实现贪心算法。 在上述运行结果中，第二次的运行结果得出的最优选择是重量=6，价值=12，但是我们可以明显的看出来最优选择应该是重量=10，价值=18.虽然重量为6的是局部最优选择，但他不是整体最优选择。 为什么会造成这种情况呢，原因在于贪心算法没有背包空间利用率的原因。运行结果得出来的背包利用率只有百分之六十，但是实际上可以增加背包的利用率。比如我们得出的整体最优选择空间的利用率达到了百分之一百。由于空间的浪费，使得它虽然是局部最优，但是却不是整体最优。 所以，贪心算法得到的结果只能说是最接近于整体最优选择。5、 OS及编译环境 Win7 64位操作系统，VC6.0的编译环境【精品文档】第 4 页