贪心算法解决背包问题

“背包问题实例-贪心算法课件” 贪心算法是一种解决问题的策略，它在每一步选择中都采取在当前状态下最好或最优的选择，希望以此达到全局最优。在背包问题中，贪心算法的应用通常是通过每次选取单位价值最高的物品来尝试达到最大的总价值。 具体到背包问题实例，这里是一个典型的0-1背包问题：有3个物品，n=3，背包的最大容量M=20，物品的重量分别为w1=18，w2=15，w3=10，对应的值分别为v1=25，v2=24，v3=15。贪心算法的解决步骤如下： 1. 首先，我们按照单位价值（值除以重量）对物品进行排序。在这个例子中，单位价值从高到低排序为：物品2（v2/w2 = 1.6），物品3（v3/w3 = 1.5），物品1（v1/w1 = 1.4）。 2. 接着，我们选取单位价值最高的物品放入背包。所以首先放入物品2，占用15的容量，价值24。 3. 计算背包剩余空间，此时剩余容量为M - w2 = 5。 4. 在剩余的物品中选取单位价值最高的，即物品3，但只能放入背包剩余的空间，因此物品3只能放入1/2，价值为7.5。 5. 最后，背包中无法再放入物品1，因为即使只放入一部分，它的单位价值也不如已部分放入的物品3。 最终，背包的总价值为24 + 7.5 = 31.5，这是按照贪心策略能得到的最大价值。然而，这不是背包问题的全局最优解，因为如果先放物品1，然后放物品3，可以得到更大的总价值32.5（物品1全放，物品3放1/2）。 贪心算法在其他问题中也有应用，例如作业安排问题、带期限的单机作业安排问题和多机调度问题。在这些问题中，贪心算法通常通过每次选择当前最优的解决方案来逼近全局最优解，但并不保证一定能得到全局最优解。 贪心算法的正确性需要通过证明来确保。对于某些问题，贪心策略确实能导致全局最优解，但对于背包问题这样的组合优化问题，贪心算法往往只能找到近似解。在设计贪心算法时，需要定义一个贪心准则，这个准则能够在每一步选择中指导决策，以期望达到全局最优。 总结来说，贪心算法是一种局部最优策略，适用于解决一些优化问题，尤其是在有明确的局部最优选择标准时。然而，它并非适用于所有问题，特别是当全局最优解需要考虑所有可能的组合时。在实际应用中，需要根据问题的具体性质来判断贪心算法是否适用。