貪心方法最優(yōu)解的證明

1、最優(yōu)解的證明最優(yōu)解的含義：在滿足約束條件的情況下，可使目標(biāo)函數(shù)取極（大或?。┲档目尚薪?。貪心解是可行解，故只需證明：貪心解可使目標(biāo)函數(shù)取得極值。1）最優(yōu)解證明思路：l 比較貪心解x與任一最優(yōu)解yl 若x與y不等，則尋找第一個(gè)不同元素的位置，假設(shè)為xil 替換最優(yōu)解y的元素yi為xi，得到新的最優(yōu)解zl 證明: z與y相比，目標(biāo)函數(shù)值沒有變化l 反復(fù)以上這種代換，直到新產(chǎn)生的最優(yōu)解與貪心解x相等，即貪心解即最優(yōu)解2）定理3.1及其證明定理3.1 如果p1/w1 p2/w2 pn/wn,則算法GREEDY-KNAPSACK對(duì)于給定的背包問題實(shí)例生成一個(gè)最優(yōu)解。證明：設(shè)X=(x1, x2, , xn

2、)是GRDDDY-KNAPSACK所生成的貪心解。 如果x1 = x2 = = xn = 1，則顯然為最優(yōu)解，得證。 否則，則存在Y=(y1, y2, , yn)是背包問題的最優(yōu)解，且有：= MStep 1 找到X與Y第一個(gè)不等的元素所在的位置k，并將yk 替換為 xk12knXx1x2xkxnYy1y2ykynZz1z2zkznxi = yi = zi (i<k)；zk=xk；Step 2 計(jì)算Z的效益值，需要證明Z的效益值大于等于Y的效益值=z1p1 + + zk-1pk-1 + zkpk + zk+1pk+1 + +znpn =y1p1 + + yk-1pk-1 +zkpk+zk+

3、1pk+1+znpn=y1p1 + + ynpn (ykpk + + ynpn)+zkpk+zk+1pk+1+znpn= + pk(zk-yk) pk+1(yk+1-zk+1)+.+ pn(yn-zn)= + wk (zk-yk) (pk/wk) wk+1 (yk+1-zk+1) (pk+1/wk+1)+.+wn (yn-zn) (pn/wn)(pk/wk >= pk+1/wk+1 >=>= pn/wn) >= + wk (zk-yk) (pk/wk) wk+1 (yk+1-zk+1) (pk/wk)+.+wn (yn-zn) (pk/wk) = + (pk/wk)wk

4、 (zk-yk) Step3 分析上式：如果能證明zk>yk，則yk增加到zk，那么必須從（yk+1，yn）中減去同樣多的量，保證總?cè)萘咳匀皇荕。從而有wk (zk-yk) =，即wk (zk-yk) =0Step4證明zk>yk，即：xk>yk由貪心解算法，X的序列形式如下：j是使得xj <> 1的最小下標(biāo)，0<=xj<112j-1jj+1nX1111xj000Y111ykynY21111ykyk+1ynY31111xj0ykynY1、Y2、Y3分別為j和k相對(duì)位置不同的三種情況：1) k<j；xk=1，xk<>yk，0<=yk<=1因此 xk>yk得證。2) k=j；M=w1x1+wj-1xj-1+wjxjM=w1x1+wj-1xj-1+wjyj+wnyn如果xj<yj則>M，不成立只有xj>yj成立3) k>j；則xk=0，yk>=0，yk<>xk，因此，yk>xkM=w1x1+wj-1xj-1+wjxjM=w1x1+wj-1xj-1+wjxj+wkyk+wnxn同樣&