資源描述：
《算法分析與設計2006第e講》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、上次內(nèi)容：(1)圖著色不能多項式時間近似到小于，TSP問題不能多項式時間近似到任意常數(shù)。(2)，時間復雜度O(mK+nlogn)，K越大求解優(yōu)化程度越高，1+e，T=O()。M是常數(shù)時可以認為是多項式時間近似方案。什么是多項式時間近似方案：定義7.2：若問題p的近似算法A(e)若滿足對任意實例I任意e>0(1)RA(e)[I]<1+e；(2)A(e)的時間復雜度是I輸入長度的多項式函數(shù)。則A(e)稱為求解問題p的多項式時間近似方案。解釋：(1)1+e很容易說明，但后面的多項式需要解釋,時間復雜度一定與e有關。近似性能比1+e，時間復雜度為：O
2、()，O(n)，O(n2)，PTAS。特殊情況：O()等等，各種情況。一定是e越小，時間復雜度越大。最后一種情況又稱為完全多項式時間近似方案。FPTAS完全多項式時間近似方案：近似度1+e；時間復雜度：P(n,)，P(·,·)是多項式函數(shù)。(2)為什么叫多項式近似方案，而不叫多項式近似算法。因為e沒有確定大小，只有程序運行時才能確定。再考慮背包問題：設計真正的多項式時間近似方案。，xi?{0,1},I=1,…,n設元素：a1,a2,…,an
3、p1,p2,…,pn
4、w1,w2,…,wn(1)簡單算法描述先挑k個元素放入背包，然后調(diào)用前面7.1節(jié)
5、算法選擇其他元素裝包。兩種規(guī)則，價值重量比大者優(yōu)先；價值大者優(yōu)先，二者擇優(yōu)選一為最終解。這樣裝法顯然不一定多么好，若對任意一種k個元素的組合都先放入背包嘗試，則最后結(jié)果一定比直接裝入好。全部嘗試完后選擇最好的，作為最后結(jié)果。算法描述：Proceduree-approx(P,W,M,n,K)1Pmax=0;2forallcombinationsIofsize￡Kandweight￡Mdo//不超過K元素的組合3PI=;4Pmax=max{Pmax,PI+L(I,P,W,M,n)}//L(I,P,W,M,n)是子程序。用于計算剩余容量裝包。5en
6、dfor6end下面這個算法是先試裝k個后再繼續(xù)裝ProcedureL(I,P,W,M,n)//I是已經(jīng)裝入的元素集合(1)S=0;T=M-;IS=?(2)Fori=1tondo(3)Ifi?IandWi￡Tthen(4)S=S+Pi;T=T-Wi;IS=IS+{i}(5)Endif(6)EndforReturn(max{S,max{Pi
7、i?I,1￡i￡n}})//S是由第一種策略裝進包的，后面是第二種策略裝進包的，比較取優(yōu)。End例子：n=8，M=110。P1P2P3P4P5P6P7P811213133435355651112123334
8、34555上面已經(jīng)按照價值重量比排好序了。(1)K=0時，直接從頭開始裝入：x1,x2,x3,x4,x5,x6,x7,x8=11111000，前5個裝入背包Pmax=11+21+31+33+43=139W=1+11+21+23+33=89(2)K=1，時，先裝入1個，再裝入其他，得到1,2,3,4,7最好x1,x2,x3,x4,x5,x6,x7,x8=11110010Pmax=11+21+31+33+45=151W=1+11+21+23+45=101(3)k=2，先裝入2個，再裝入其他，得到1,2,3,5,6最好x1,x2,x3,x4,x5,
9、x6,x7,x8=1,1,1,0,1,1,0,0Pmax=11+21+31+43+53=159W=109=1+11+21+33+43這是最優(yōu)解。定理7.15設背包問題最優(yōu)解為P*，Pmax是前述先裝算法e-approx得到的解，則對任意背包問題實例均成立。證明：//為什么會很好呢？因為有可能將最優(yōu)解前K個價值最大的先裝入。(1)給定實例，設R是該實例最優(yōu)解的裝入背包元素下標集合，若
10、R
11、￡K，則能夠求到最優(yōu)解，以下假設
12、R
13、>K。(2)將R中的元素的價值重量寫成有序?qū)Γ凑找韵乱?guī)則重新排序：(),(),…,()
14、
15、(),…,()。(*),…,
16、是R中元素前k個最大價值，3…33，1￡j￡
17、R
18、-k。(*)從i=k+1開始按照價值重量比排序3…3。(3)考慮先將R中前K個元素裝入背包的情況，有一種這樣情況。PI=設S是調(diào)用L(I,P,W,M,n)增加的收益。會不會將R中元素全部裝入包？則：P*19、ax3PI+L，這僅是一種情況得到裝包收益為PI+S，算法是所有情況都試遍得到的解，結(jié)果不會比這次差。，m>k,S3，Pmax3(K+1)所以前面的不等式成立。沒有
