代替y进行上面的讨论，以我们又可以找到新的解向量z，如此等等，由于分量的个数
有限，必到某一步停止，最后找到解向量y它和x有相同的分量，又与y有不同的总价值（大
f4
于x的总价值），矛盾。这个矛盾源于x不是最优解的假设。故，x是最优解。证毕贪心算法主要用于处理优化问题。每个优化问题都是由目标函数和约束条件组成。满足约束条件的解称为可行解，而那些使得目标函数取得最大（最小）值的可行解称为最优解。如背包问题是一个优化问题，式53中的函数是目标函数，而54式描述的要求是约束条件，这里优化是使目标函数取最大值。贪心算法在每一步的决策中虽然没有完全顾忌到问题整体优化，但在局部择优中是朝着整体优化的方向发展的。为此，贪心算法首先要确定一个度量准则（称为贪心准则），每一步都是按这个准则选取优化方案。如背包问题的贪心准则是选取选取最大物品；而装载问题的贪心的准则是选取最轻的货箱；选取最轻的货箱；单位价值pw最大物品；选取最轻的货箱找零钱问题所用的贪心准则是选取面值最大的硬币。对于一个给定的问题，初看起来，往选取面值最大的硬币。选取面值最大的硬币往有若干种贪心准则可选，但在实际上，其中的多数都不能使贪心算法达到问题的最优解。如背包问题的下面实例：
3M20p252415w181510如果以价值最大为贪心准则，则贪心算法的执行过程是：首先考虑将物品1装包，此时获得效益值25，包的剩余容量是2。然后考虑将物品2装包，但物品2的重量15超出包的剩余容量，只能装入该种物品的215，此时获得的总效益值为2524×215282。这样得到的可行解（1，215，0）并不是最优解。事实上，如果以单位价值最大为贪心准则，则贪心算法的执行过程是：先计算出各个物品的单位价值25182415151013891615。首先考虑单位价值大的物品装包，即将物品2装包，此时获得效益值24，背包的剩余容量是5。然后考虑装物品3，由于物品3的重量超出背包的剩余容量，只能装入该物品51512至此背包已经装满，所得的总的效益值为24152315。比前面的装法的效益值大。实践证明，选择能产生最优解的贪心准则是设计贪心算法的核心问题。以下给出贪心算法流程的伪代码。程序512贪心算法抽象化控制流程
GreedyA
A1
代表那个输入solutio
解向量初始化为空集forifrom1to
doxSelectAifFeasiblesolutio
xthe
solutio
U
io
solutio
xe
dife
dfor
f5
retur
solutio
e
dGreedy这里SelectA是按照贪心r