贪心法求解背包问题.pptVIP

贪心法求解背包问题 问题描述 　　　已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为。假定将物品i的一部分放入背包就会得到的效益，这里，, 。显然，由于背包容量是M，因此，要求所有选中要装入背包的物品总重量不得超过M.。如果这n件物品的总重量不超过M，则把所有物品装入背包自然获得最大效益。现需解决的问题是，在这些物品重量的和大于M的情况下，该如何装包，使得得到更大的效益值。由以上叙述，可将这个问题形式表述如下： 　　　极 大 化目标函数 　　　约束条件 算法分析 　　　首先需确定最优的量度标准。这里考虑三种策略： 　　　策略1：按物品价值p降序装包， 　　　策略2：按物品重w升序装包 　　　策略3：按物品价值与重量比值p/w的降序装包 分别以上面三种策略分别求以下情况背包问题的解： 　　　n=7，M=15， 　　　（ ）=（10，5，15，7，6，18，3） 　　　（ ）=（2，3，5，7，1，4，1） 策略1：按物品价值p降序装包，ｐ＝｛ｐ６,ｐ３,ｐ１，ｐ４，ｐ５,ｐ２,ｐ７｝，先放,4个p6,，再放入5个p3，放入2个p1，最后放入4个p4。总的重量Ｍ＝１５，总价值Ｗ＝４×１８＋１５×５＋１０×２＋７×４＝１９５ 　　　　策略２：按物品重w升序装包，ｗ＝｛ｗ５,ｗ７，ｗ１,ｗ２,ｗ６,ｗ３,ｗ４｝，依次放入ｗ５,ｗ７，ｗ１,ｗ２,ｗ６，再放入４个ｗ３，总的重量Ｍ＝１５，总价值Ｗ＝１×６＋１×３＋２×１０＋３×５＋４×１８＋４×１５＝１７６ 　　策略３：按物品价值与重量比值p/w的降序装包，ｐ／ｗ＝｛6,5，9/2,3,3,5/3,1｝，依次放入ｗ5,ｗ1，ｗ6,ｗ3,ｗ7，再放入2个ｗ2，总的重量Ｍ＝１５，总价值Ｗ＝2×10＋2×5＋5×15＋1×6＋4×18＋1×3＝256 算法描述 procedure GREEDY-KNAPSACK(P,W,M,X,n) //P（1：n）和W（1：n）分别含有按P（i）/W（i）≥P（i+1）/ W （i+1）排序的n件物品的效益值和重量。M是背包的容量，而X（1：n）是解向量。// real P(1：n)，W（1：n）,X（1：n），M，cu； 　　 integer i，n; 　　　　　X0 //将解向量初始化为零 　　　　　　　　　cuM //cu是背包剩余容量 　　　　　　　　　for i1 to n do 　　　　　　　　 if W(i)cu then exit endif 　　　　　　　　 X(i) 1 　　　　　　　　 cucu-W(i) 　　　　　　　　　repeat 　　　　　　　　　if i≤n then X(i) cu/W(i) 　　　　　　　　　endif 　　　　　　　　end GREEDY-KNAPSACK 算法思想 贪心算法采用逐步构造最优解的方法，在每个阶段，都在一定的标准下做出 一个看上 去最优的决策，0/1背包选择单位效益最高贪心准则，即从剩余物品中选择可装入包的Pi/Wi值最大的物品。 　　 算法分析 贪心法解决0/1背包问题主要代价是花费在p/w的排序上。由程序可以知道冒泡排序的时间复杂度为（N2）。它也是整个程序的时间复杂度。贪心法可以很快的解决问题，但是它不一定能够得到最优解，寻找一个好的贪心法则在贪心法处理中是至关重要的。 与其他算法比较 1.贪心法：处理问题的速度快，思想简单。使用该方法的必要条件是寻找好的贪心法则。不足之处在于很多时候它只能求的似优解，却不能求的最优解 2.动态规划法：可以求解最优解，重点在于徐兆最优决策序列但是速度较慢。 3.分支限界法：可以求解最优解，重点在于寻找限界值。易求最优解，但是空间花费较高，效率不是很高。 选择哪一种算法，不仅要根据问题本身还需要考虑到其他因素，例如时间复杂度，空间复杂度，易求解等等因素。 结果 The end,thank you! 请提问！