算法分析与设计-贪心算法求解背包问题.docx

用贪心算法求解背包问题 D 软件 101 薛思雨 511020825 一、贪心算法介绍 顾名思义， 贪心算法总是作出在当前看来最好的选择。 也就是说贪心算法并不从整体最 优考虑， 它所作出的选择只是在某种意义上的局部最优选择。 当然， 希望贪心算法得到的最 终结果也是整体最优的。 虽然贪心算法不能对所有问题都得到整体最优解， 但对许多问题它 能产生整体最优解。 如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算 法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法求解的问题一般具有两个重要性质： 贪心选择性质和最优子结构性质。 所谓贪 心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择， 即贪心选择来达 到。 这是贪心算法可行的第一个基本要素， 也是贪心算法与动态规划算法的主要区别。 当一 个问题的最优解包含其子问题的最优解时， 称此问题具有最优子结构性质。 问题的最优子结 构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 二、贪心法的基本思路 从问题的某一个初始解出发逐步逼近给定的目标， 以尽可能快的地求得更好的解。 当达 到某算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 不能保证求得的最后解是最佳的； 不能用来求最大或最小解问题； 只能求满足某些约束条件的可行解的范围。 三、关于贪心算法在背包问题中的应用的探讨 问题描述： 0-1 背包问题：给定 n 种物品和一个背包。物品 i 的重量是 Wi ，其价值为 Vi ，背包的容量为 C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大 ？在选择装入背包的物 品时， 对每种物品 i 只有 2 种选择，即装入背包 (1)或不装入背包 (0)。不能将物品 i 装入背包 多次，也不能只装入部分的物品 i。 背包问题：与0-1背包问题类似，所不同的是在选择物品 i装入背包时，可以选择物品 i的 一部分，而不一定要全部装入背包， K i n。 贪心算法解决背包问题有几种策略： 一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规 则，价值最大的物品首先被装入(假设有足够容量) ，然后是下一个价值最大的物品，如此 继续下去。 这种策略不能保证得到最优解。 例如， 考虑 n=2, w=[100,10,10], p =[20,15,15], c = 105。当利用价值贪婪准则时，获得的解为 x= [ 1 , 0 , 0 ]，这种方案的总价值为 2 0。而最优 解为[ 0 , 1 , 1 ]，其总价值为 3 0。 另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽 然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑 n= 2 ,w=[10,20], p=[5,100], c= 2 5 。当利用重量贪婪策略时， 获得的解为 x =[1,0], 比最优解 [ 0 , 1 要差。 还有一种贪婪准则，就是我们教材上提到的，认为，每一项计算 yi=vi/si, 即该项值和大 小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次类推，尽可能 的多放，直到装满背包。 有的参考资料也称为价值密度 pi/wi 贪婪算法。这种策略也不能保证得到最优解。利用此策 略试解 n= 3 ,w=[20,15,15], p=[40,25,25], c=30 时的最优解。虽然按 pi /wi 非递(增)减的次 序装入物品不能保证得到最优解，但它是一个直觉上近似的解。 而且这是解决普通背包问题的最优解，因为在选择物品 i 装入背包时，可以选择物品 i 的一 { { 容量跳出 部分，而不一定要全部装入背包， K i n。 贪心算法解决背包问题的算法实现： #include iostream using namespace std; struct goodinfo { float p; // 物品效益 float w; // 物品重量 float X; // 物品该放的数量 int flag; // 物品编号 };// 物品信息结构体 void Insertionsort(goodinfo goods[],int n) { int j,i; for(j=2;j=n;j++) { goods[0]=goods[j]; i=j-1; while (goods[0].pgoods[i].p) { goods[i+1]=goods[i]; i--; } goods[i+1]=goods[0]; } }// 按物品效益，重量比值做升序排列 void bag(goodinfo goods[],float M,int n) { float cu; int i,j; for(i=1;i=