选择。例如找零钱问题中,售货员每捡一个硬币都想着使自己手中的 钱尽快达到需要找钱的总数。在装载问题中,每装一个货箱都想着在 不超重的前提下让船装进更多的箱子。但是贪心方法并未考虑整体最 优解,它所作出的选择只是在某种意义上的局部最优选择。当然,在 采用贪心算法时未必不希望结果是整体最优的。事实上,有相当一部 分问题,采用贪心算法能够达到整体最优。如前面的找零钱问题以及 后面将要讲到的单点源最短路径问题、最小生成树问题、工件排序问 题等。为了更好理解贪心算法,我们将装载问题稍加推广,考虑O/1 背包问题。 0/1背包问题已知容量为M的背包和n件物品。第i件物品的 重量为w,价值是p。因而将物品i的一部分x放进背包即获得px 的价值。问题是:怎样装包使所获得的价值最大。即是如下的优化问 题 max∑px (53) ∑x1≤M l≤i≤n 0≤x1≤1,P1>0,w1>0,1≤i 采用贪心方法,有几种原则可循:a.每次捡最轻的物品装;b.每次捡 价值最大的装;c每次装包时既考虑物品的重量又考虑物品的价值 也就是说每次捡单位价值p1/w1最大的装。按原则a来装只考虑到多 装些物品,但由于单位价值未必高,总价值不能达到最大;按原则b 来装,每次选择的价值最大,但同时也可能占用了较大的空间,装的 物品少,未变能够达到总价值最大。比较合理的原则是c。事实上,选择。例如找零钱问题中，售货员每捡一个硬币都想着使自己手中的 钱尽快达到需要找钱的总数。在装载问题中，每装一个货箱都想着在 不超重的前提下让船装进更多的箱子。但是贪心方法并未考虑整体最 优解，它所作出的选择只是在某种意义上的局部最优选择。当然，在 采用贪心算法时未必不希望结果是整体最优的。事实上，有相当一部 分问题，采用贪心算法能够达到整体最优。如前面的找零钱问题以及 后面将要讲到的单点源最短路径问题、最小生成树问题、工件排序问 题等。为了更好理解贪心算法，我们将装载问题稍加推广，考虑 0/1 背包问题。 0/1 背包问题 已知容量为 M 的背包和 n 件物品。第 i 件物品的 重量为 wi，价值是 pi。因而将物品 i 的一部分 xi放进背包即获得 pixi 的价值。问题是：怎样装包使所获得的价值最大。即是如下的优化问 题： ∑ ≤i≤n i i p x 1 max (5.3) x p w i n w x M i i i i n i i ≤ ≤ > > ≤ ≤ ∑ ≤ ≤ ≤ 0 1, 0, 0, 1 1 (5.4) 采用贪心方法，有几种原则可循：a.每次捡最轻的物品装；b.每次捡 价值最大的装；c.每次装包时既考虑物品的重量又考虑物品的价值， 也就是说每次捡单位价值 i wi p 最大的装。按原则 a 来装只考虑到多 装些物品，但由于单位价值未必高，总价值不能达到最大；按原则 b 来装，每次选择的价值最大，但同时也可能占用了较大的空间，装的 物品少，未变能够达到总价值最大。比较合理的原则是 c。事实上