背包问题(贪心算法)

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

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

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

3、printf("%.2f",Node[i].value);1〃）；Jprintf(〃〃)；for(i=0;i

4、tf(/z第j次选择为:%.2f",curvalue);j++；}}C:UserssummyDesktop1背包问题贪心请输入背包容积：10请输入物品个数：5物品的价重比从高到低依次排列为:2.007.009.005.007.000.005.008.005.008.00选中物品的价格为：第1次选择后，价格为：2.00第2次选择后，价格为：9.00第3次选择后，价格为：14.00测试结果C:UserssummyDesktop1背包问遞貪心.exe青输入背包容和：30青输入物品个数：3期品的价重比从高到低依次排列为:7・009.007

5、.005.008.008.00选中物品的价格为:第1次选择后，价格为：7.00第2次选择后，价格为：16.00第3次选择后，价格为：23.008.007.004.008.009.009.007.005.006.004.005.001.002.001.001.000.003.003.002.005.008.008.007.005.009.007.009.002.008.006.007.006.00附录：完整代码^include★include^includestructnode{floatvalue;f

6、loatweight;};floatValue,curvalue=O;floatWeight,curweight二0;〃按价重比冒泡排序voidsort(nodeNode[],intM){inti,j；nodetemp;for(i=0;i

7、的价重比从高到低依次排列为:3;for(i=0;i

8、;curweight+=Node[i].weight;printfC第j次选择为