证明的基本思想: 将此贪心解与(假设中的)任一最优解相比较 ●如果这两个解相同,则显然贪心解就是最优解。 ●如果这两个解不同,就设法去找两者开始不同的第一个分量位置i, 然后设法用贪心解的这个去替换最优解对应的分量,并证明最优 解在分量代换前后总的效益值没有任何变化(且不违反约束条件) 然后比较二者。若还不同,则反复进行代换,直到代换后产生的 最 优解”与贪心解完全一样 ●在上述代换中,最优解的效益值没有任何损失,从而证明贪心解的 效益值与代换前后最优解的效益值相同。即,贪心解如同最优解一 样可取得目标函数的最大/最小值。 从而得证:该贪心解即是问题的最优解
证明的基本思想： 将此贪心解与（假设中的）任一最优解相比较。 ● 如果这两个解相同，则显然贪心解就是最优解。 ● 如果这两个解不同，就设法去找两者开始不同的第一个分量位置i， 然后设法用贪心解的这个xi去替换最优解对应的分量 ，并证明最优 解在分量代换前后总的效益值没有任何变化(且不违反约束条件)。 ● 然后比较二者。若还不同，则反复进行代换，直到代换后产生的 “最 优解”与贪心解完全一样。 ● 在上述代换中，最优解的效益值没有任何损失，从而证明贪心解的 效益值与代换前后最优解的效益值相同。即，贪心解如同最优解一 样可取得目标函数的最大/最小值。 从而得证：该贪心解即是问题的最优解
定理31如果pW1≥p2W2≥.≥pnM,则算法 GREEDY KNAPSACK对于给定的背包问题实例生成一个最优解。 证明 设X=(x1,x2,…,x)是 GREEDY-KNAPSACK所生成的贪心 解 ①如果所有的x都等于1,则显然X就是问题的最优解。否则, ②设是使X≠1的最小下标。由算法的执行过程可知, X=11s<, 0≤X<1 X=0 isn
定理3.1 如果p1 /w1≥ p2 /w2≥…≥ pn /wn ,则算法GREEDYKNAPSACK对于给定的背包问题实例生成一个最优解。 证明： 设X=(x1 , x2 , …, xn )是GREEDY-KNAPSACK所生成的贪心 解。 ① 如果所有的xi都等于1,则显然X就是问题的最优解。否则， ② 设j是使xi≠1的最小下标。由算法的执行过程可知， ⚫ xi=1 1≤i＜j, ⚫ 0≤xj ＜1 ⚫ xi=0 j＜i≤n
假设Y是问题的最优解:Y=(y1,y2,…,y)且有: ●若Ⅹ=Y,则X就是最优解。否则 ●X和Y至少在1个分量上存在不同 设k是使得y≠ⅹ的最小下标,则有y<×。可分以下情 况说明: a)若kj,则x=1。因为y≠x,从而有y<x b)若k,由于∑wx=M,且对1<j,有y=X=1,而对j <sn,有x=0;故此时若y>×,则将有∑wx>M与Y是可 行解相矛盾。而y≠X,所以y<x C)若k习j,则∑wx>M,不能成立
假设Y是问题的最优解：Y=(y1 , y2 , …, yn ) 且有： ● 若X ＝ Y，则X就是最优解。否则， ● X和Y至少在1个分量上存在不同。 设k是使得yk≠ xk的最小下标，则有yk＜ xk。可分以下情 况说明： a) 若k<j，则xk=1。因为yk≠ xk ,从而有yk ＜ xk b) 若k=j，由于 ，且对1≤i＜j，有yi=xi=1,而对j ＜i≤n,有xi＝0；故此时若yk＞xk，则将有 ，与Y是可 行解相矛盾。而yk≠ xk ,所以yk ＜ xk c) 若k＞j，则 ，不能成立 wi xi = M wi yi M wi yi M wi yi = M
在Y中作以下调整:将y增加到x,因为y<X,为保持解的可行性, 必须从(yk+1y中减去同样多的量。设调整后的解为Z=(21,z2,…,z), 其中z=X,1≤≤k,且有:∑w(y-=,)=k(=k-yk) k<i≤ Z的效益值有 ∑P=,=∑Py+(=k-y)Pk/wk-∑(y-=,)m,P, ≥∑Py+(=k-yk)k-∑(-=,mPk/k l≤i≤n k<i≤n ∑ piy 差值=0
在Y中作以下调整：将yk增加到xk，因为yk＜xk ,为保持解的可行性， 必须从(yk+1,…,yn )中减去同样多的量。设调整后的解为Z=(z1 , z2 , …, zn )， 其中zi＝xi，1≤i≤k，且有： Z的效益值有： − = − k i n i i i k k yk w (y z ) w (z ) = + − − − i n i i i k i n i i k k k k k i i i n pi zi p y z y w p w y z w p w 1 1 ( ) / ( ) / + − − − i n i k k k i n pi yi zk yk wk yi zi w p w 1 [( ) ( ) ] / = i n i i p y 1 差值＝0
由以上分析得, 若∑n=,>∑ny,则Y将不是最优解; 若∑=,=∑p;,则或者Z=X,则X就是最优解; ■或者Z,则重复以上替代过程,或者证明Y不是最优 解,或者把Y转换成X,从而证明Ⅹ是最优解
由以上分析得， ◼ 若 ，则Y将不是最优解； ◼ 若 ，则或者Z=X，则X就是最优解； ◼ 或者Z≠X，则重复以上替代过程，或者证明Y不是最优 解，或者把Y转换成X，从而证明X是最优解 i i pi yi p z i i = pi yi p z