数n有限,必到某一步停止,我们能找到解向量y*,它和x有相同的 分量,又与y又有相同的总价值(大于x的总价值),矛盾。这个矛 盾源于ⅹ不是最优解的假设。故,x是最优解。 贪心算法主要用于处理优化问题。每个优化问题都是由目标函数 和约東条件组成。满足约束条件的解称为可行解,而那些使得目标函 数取极值的可行解称为最优解。如0/背包问题是一个优化问题,式 (53)中的函数是目标函数,而(54)式描述的要求是约束条件,这里优 化是使目标函数取最大值。贪心算法在每一步的决策中虽然没有完全 顾忌到问题整体优化,但在局部择优中是朝着整体优化的方向发展 的。为此,贪心算法首先要确定一个度量准则,每一步都是按这个准 则选取优化方案。如0/1背包问题的贪心准则是选取单位价值pw最 大物品,而装载问题的贪心算法选取的准则是选取最轻的货箱,找零 钱问题所用的贪心准则是选取面值最大的硬币。对于一个给定的问 题,初看起来,往往有若干中贪心准则可选,但在实际上,其中的多 数都不能使贪心算法达到问题的最优解。如O/1背包问题下面的实例: n=3,M=20,p=(25,24,15),w(18,15,10) 如果以价值最大为贪心准则,则贪心算法的执行过程是:首先考虑将 物品1装包,此时获得效益值25,包的剩余容量是2。然后考虑将物 品2装包,但物品2的重量15超出包的剩余容量,只能装入该种物 品的2/15,此时获得的总效益值为25+24×2/15=282。这样得到的可 行解(1,2/15,0)并不是最优解。事实上,如果以单位价值最大为 贪心准则,则贪心算法的执行过程是:先计算出各个物品的单位价值数 n 有限，必到某一步停止，我们能找到解向量 y*,它和 x 有相同的 分量，又与 y 又有相同的总价值（大于 x 的总价值），矛盾。 这个矛 盾源于 x 不是最优解的假设。故，x 是最优解。 贪心算法主要用于处理优化问题。每个优化问题都是由目标函数 和约束条件组成。满足约束条件的解称为可行解，而那些使得目标函 数取极值的可行解称为最优解。如 0/1 背包问题是一个优化问题，式 (5.3)中的函数是目标函数，而(5.4)式描述的要求是约束条件，这里优 化是使目标函数取最大值。贪心算法在每一步的决策中虽然没有完全 顾忌到问题整体优化，但在局部择优中是朝着整体优化的方向发展 的。为此，贪心算法首先要确定一个度量准则，每一步都是按这个准 则选取优化方案。如 0/1 背包问题的贪心准则是选取单位价值 p/w 最 大物品，而装载问题的贪心算法选取的准则是选取最轻的货箱，找零 钱问题所用的贪心准则是选取面值最大的硬币。对于一个给定的问 题，初看起来，往往有若干中贪心准则可选，但在实际上，其中的多 数都不能使贪心算法达到问题的最优解。如 0/1 背包问题下面的实例： n=3, M=20, p=(25, 24, 15), w=(18,15,10) 如果以价值最大为贪心准则，则贪心算法的执行过程是：首先考虑将 物品 1 装包，此时获得效益值 25，包的剩余容量是 2。然后考虑将物 品 2 装包，但物品 2 的重量 15 超出包的剩余容量，只能装入该种物 品的 2/15，此时获得的总效益值为 25+24×2/15=28.2。这样得到的可 行解（1，2/15，0）并不是最优解。事实上，如果以单位价值最大为 贪心准则，则贪心算法的执行过程是：先计算出各个物品的单位价值