贪心法解决背包问题(共7页)

1、精选优质文档-倾情为你奉上算法分析实验报告贪心法解决背包问题学生姓名： 专 业： 班 级： 学 号: 指导教师： 2017年 6月12日目录一、实验题目贪心法解决背包问题二、实验目的1）以背包问题为例，掌握贪心法的基本设计策略。2）熟练掌握各种贪心策略情况下的背包问题的算法并实现；其中：量度标准分别取：效益增量v、物品重量w、v/ w比值；3) 分析实验结果来验证理解贪心法中目标函数设计的重要性。三、实验要求1.问题描述：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 与0-1背包问题类似，所不同的是在选择物

2、品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，但不可以重复装入。2.算法：贪心法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。该算法存在问题：1）不能保证求得的最后解是最佳的；2）不能用来求最大或最小解问题；3） 只能求满足某些约束条件的可行解的范围。四、实现过程1、实验设计：1.用贪心法求解背包问题的关键是如何选定贪心策略，使得按照一定的顺序选择每个物品，并尽可能的装入背包，直至背包装满。至少有三种看似合理的贪心策略：1）按物品价值v降序装包，因为这可以尽可能快的增加背包的总价值。但是，

3、虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗太快，使得装入背包得物品个数减少，从而不能保证目标函数达到最大。2）按物品重量w升序装包，因为这可以装入尽可能多的物品，从而增加背包总价值。但是，虽然每一步选择使背包得容量消耗得慢了，但背包价值却没能保证迅速增长，从而不能保证目标函数达到最大。3）按物品价值与重量比值v/w的降序装包。2.设背包容量为C，共有n个物品，物品重量存放在数组wn中，价值存放在数组vn中，问题的解存放在数组xn中，贪心法求解背包问题的算法如下。输入：背包容量为C，物品重量wn，物品价值vn输出：数组xn1） 改变数组w和v的排列顺序，使其按单位重量价值vi/

4、wi降序排列；2） 将数组xn初始化为0；3） i=0；4） 循环直到（wi>C）a. 将第i个物品放入背包：xi=1;b. C=C-wi;c. i+;5） xi=C/wi。3.流程图物品iwi>Cxi=1C=C-wii+i<n退出循环inxi=C/wi程序结束4.算法实现int KnapSack(int n,int w,int v,int C)double x10=0;int maxValue=0;for (int i = 0; wi < C; i+)xi=1;maxValue+=vi;C=C-wi;xi=(double)C/wi;maxValue+=xi*vi;return maxValue;2、调试分析在算法KnapSack中，时间主要消耗在将各种物品按照单位重量的价值从大到小排序。因此，其时间复杂度为O(nn)。3、运行结果：4、实验总结： 通过本次实验我们了解了背包问题贪心法的基本思想和策略，我们发现用该方法解决此问题的核心在于对量度标准的选择，通过具体数据的解答，我们最终确定了以单位效益，即物品的权值和重量的比值为量度最终能得到背包问题贪心法的最优解，同时也使我们对贪心法这一策略有了更为直观的认识。五、参考文献1 王红梅 胡胡算法设