背包问题(贪心算法).docx

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

1、算法分析与设计实验报告第4次实验姓名学号班级时间11.14下午地点四合院实验名称贪心算法实验（求解背包问题）实验目的1.通过上机实验，要求掌握贪心算法的问题描述、算法设计思想、程序设计。2.设计程序，利用贪心算法求解背包问题，输出相应结果，并计算出程序运行所需要的时间。实验原理给定几组数据，利用贪心算法的思想，将物品装入背包并使得其价值最大。实验步骤①计算每种物品单位重量的价值Vi/Wi.②依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。③若将这种物品全部装入背包后，背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。④依此

2、策略一直地进行下去，直到背包装满为止。关键代码//按价重比冒泡排序voidsort(nodeNode[],intM){inti,j;nodetemp;for(i=0;i

3、intf("%.2f",Node[i].value);}printf("");for(i=0;i

4、.2f",curvalue);j++;}}}测试结果实验心得通过这次实验，我回顾了贪心算法实现背包问题，在其中加入了舍伍德随机化过程得到物品的价格和重量，取值更加均匀，让我熟悉了随机化算法，使结果更可靠。贪心算法与动态规划有所不同，贪心算法要求每一步的选择都是当前最优的解，刚开始时，我编写的代码选择的是选择物品中价值最高的，后来发现忽视了重量，更改后每一步的最优解应该是选择单位重量中价值最高的物品。另外由于需要改进的地方：1.价重比排序中可以选择其他的排序方法降低复杂度。2.排序后输出时可以将重量和价格同时输出，即可减少一个循环。3.对于随机取数时，出现重量

5、为0的情况不符合现实，可以改进。实验得分助教签名附录：完整代码#include#include#includestructnode{floatvalue;floatweight;};floatValue,curvalue=0;floatWeight,curweight=0;//按价重比冒泡排序voidsort(nodeNode[],intM){inti,j;nodetemp;for(i=0;i

6、i].weight)

7、"选中物品的价格为：");for(i=0;i

8、ULL);for(i=0