第七章背包問題(第9講)

1、 第七章第七章 背包問題背包問題 Optimizing Methods第七章第七章 背包問題背包問題1 背包問題的描述背包問題的描述2 背包問題的分支定界法背包問題的分支定界法3 背包問題的近似算法背包問題的近似算法第七章第七章 背包問題背包問題 背包問題背包問題 ( Knapsack Problem ) 是一個(gè)有著廣泛應(yīng)是一個(gè)有著廣泛應(yīng)用的組合優(yōu)化問題，它不僅在投資決策、裝載、庫存等用的組合優(yōu)化問題，它不僅在投資決策、裝載、庫存等方面有應(yīng)用，而且常以子問題形式出現(xiàn)在大規(guī)模優(yōu)化問方面有應(yīng)用，而且常以子問題形式出現(xiàn)在大規(guī)模優(yōu)化問題中，它的理論與算法具有一定的代表性題中，它的理論與算法具有一定的代

2、表性. 背包問題的一般描述為：設(shè)有物品集背包問題的一般描述為：設(shè)有物品集是一個(gè)準(zhǔn)備放入容量為是一個(gè)準(zhǔn)備放入容量為 的背包中的的背包中的 n 項(xiàng)物品的集項(xiàng)物品的集合合. 12,nUu uuCZ物品物品 的重量為的重量為 價(jià)值為價(jià)值為jujwZjpZ如何選擇如何選擇 U 中的一些物品裝入背包，使這些物品的中的一些物品裝入背包，使這些物品的總重量不超過總重量不超過 C ，且使總價(jià)值達(dá)到最大？，且使總價(jià)值達(dá)到最大？1 1 背包問題的描述背包問題的描述背包問題的數(shù)學(xué)模型：背包問題的數(shù)學(xué)模型：()KP1maxnjjjzp x1. .njjjstw xC011,2,jxorjNnjwZ重量重量jpZ價(jià)值價(jià)值

3、CZ容量容量 因?yàn)闆Q策變量因?yàn)闆Q策變量 , ,所以也稱所以也稱 0-1 0-1 背包問題背包問題. .01jxor一般背包問題一般背包問題: : 01,2,jxZjNn KPNPC( General Knapsack Problem )第七章第七章 背包問題背包問題為討論方便，總可假定（相當(dāng)于標(biāo)準(zhǔn)化）：為討論方便，總可假定（相當(dāng)于標(biāo)準(zhǔn)化）：即按價(jià)值密度從大到小排列即按價(jià)值密度從大到小排列.10,01jjwpjn、；21 ;jwCjn、13njjwC、12124nnpppwww、 實(shí)際問題實(shí)際問題并非滿足并非滿足1 1 背包問題的描述背包問題的描述對對 4 只需只需 O(nln n)次運(yùn)算即可；

4、次運(yùn)算即可；對對 3 若若最優(yōu)解為最優(yōu)解為 ;1njjwC121nxxx對對 2 若若 ，則最優(yōu)解中，則最優(yōu)解中 事先可去掉事先可去掉;jwC0,jx 對對 1 分三種情況討論分三種情況討論:00jjpw令令00,0jjNjN pw此時(shí)，最優(yōu)解中此時(shí)，最優(yōu)解中 0jx 所以，該物品事先可去掉所以，該物品事先可去掉;00jjpw令令10,0jjNjN pw此時(shí)，最優(yōu)解中此時(shí)，最優(yōu)解中 1jx 所以，該物品事先可去掉所以，該物品事先可去掉; 容量取容量取1jCCw第七章第七章 背包問題背包問題00jjpw令令0,0jjNjN pw 只需在模型中，令只需在模型中，令 ，則系數(shù)即為大于零了，則系數(shù)即為

5、大于零了.1jjxy 綜上，對不滿足（綜上，對不滿足（1）、（）、（2）、（）、（3）的假定，可）的假定，可作如下處理，使之滿足：作如下處理，使之滿足：jN1jjjjjjxyppww 01()jNNNNNjjjjjjxyppww則原問題化為：則原問題化為：1maxjjjj NNj NNzp yp1. .jjjj NNj NNstw yCw01,jyorjNN1 1 背包問題的描述背包問題的描述()KP1maxnjjjzp x1. .njjjstw xC011,2,jxorjNn如果在（如果在（KP）中，令）中，令1jjxy 11maxnnjjjjjzpp y11. .nnjjjjjstww y

6、C011,2,jyorjNn令令1njjqwC1minnjjjup y1. .njjjs tw yq011,2,jyorjNn該問題的實(shí)際意義該問題的實(shí)際意義是求不放在包中的物是求不放在包中的物品的價(jià)值和最小品的價(jià)值和最小 模型的意義模型的意義Go back第七章第七章 背包問題背包問題 分支定界法分支定界法 ( Branch and Bound Method ) 的基本的基本思想在運(yùn)籌學(xué)課程中已介紹，它的重要在于它提出了一思想在運(yùn)籌學(xué)課程中已介紹，它的重要在于它提出了一類新的思路（隱枚舉法），使得許多原來不好解決的問類新的思路（隱枚舉法），使得許多原來不好解決的問題有了解決的可能性。（具有普

7、適性）題有了解決的可能性。（具有普適性）確定問題（子問題）的最優(yōu)值的確定問題（子問題）的最優(yōu)值的界界極大（小）化問題極大（?。┗瘑栴}上（下）界上（下）界 通常是通過求解松弛問題，用松弛問題的解作為界通常是通過求解松弛問題，用松弛問題的解作為界Note 松弛問題選擇的松弛問題選擇的原則原則、松弛問題要與原問題的最優(yōu)值盡量接近；、松弛問題要與原問題的最優(yōu)值盡量接近；松弛問題要盡量容易解松弛問題要盡量容易解 . .這兩個(gè)原則不易統(tǒng)一，所以可選擇不同的松弛問題這兩個(gè)原則不易統(tǒng)一，所以可選擇不同的松弛問題2 2 背包問題的分支定界法背包問題的分支定界法劃分方法的選擇劃分方法的選擇原則是希望分出來的子問題

8、容易被查清，可加快計(jì)算原則是希望分出來的子問題容易被查清，可加快計(jì)算.選哪個(gè)活問題先檢查選哪個(gè)活問題先檢查先檢查最大上界（極大化問題）的活問題先檢查最大上界（極大化問題）的活問題優(yōu)點(diǎn)：優(yōu)點(diǎn)：檢查子問題較其他規(guī)則為少；檢查子問題較其他規(guī)則為少；缺點(diǎn)：缺點(diǎn)：計(jì)算機(jī)儲(chǔ)存量較大計(jì)算機(jī)儲(chǔ)存量較大先檢查最新產(chǎn)生的最大上界的活問題先檢查最新產(chǎn)生的最大上界的活問題優(yōu)點(diǎn)：優(yōu)點(diǎn)：計(jì)算機(jī)儲(chǔ)存量較少計(jì)算機(jī)儲(chǔ)存量較少 ；缺點(diǎn)：缺點(diǎn)：需要更多的分支運(yùn)算需要更多的分支運(yùn)算選擇的不同，提供了發(fā)揮的余地選擇的不同，提供了發(fā)揮的余地第七章第七章 背包問題背包問題考慮考慮 KP 的松弛問題的松弛問題0,10,1jjxx()C KP

9、1maxnjjjzp x1. .njjjstw xC1,2,jNn01jx0,1jx ()KPC(KP)如何求解？如何求解？思路：將物品按價(jià)值密度從大到小的順序放入包內(nèi)思路：將物品按價(jià)值密度從大到小的順序放入包內(nèi), 記記 1minjiisjwC 關(guān)鍵項(xiàng)關(guān)鍵項(xiàng)第一個(gè)放不下的第一個(gè)放不下的物品的序號物品的序號?Theorem 2.12 2 背包問題的分支定界法背包問題的分支定界法C(KP) 最優(yōu)解為最優(yōu)解為111jxjs01jxjsn ssCxw其中其中11sjjCCw最優(yōu)解值為最優(yōu)解值為11()ssoptjjspzC KPpCwproof 顯然，顯然， ，()( ()optoptzKPzC KP

10、jp由于由于 的整數(shù)性，的整數(shù)性，得到得到 z ( KP ) 的一個(gè)上界：的一個(gè)上界：111( ()ssoptjjspUzC KPpCw表示不超過表示不超過 的最大整數(shù)的最大整數(shù). .Go on Go back第七章第七章 背包問題背包問題Theorem 2.1 的證明的證明顯然顯然 C(KP) 的最優(yōu)解必滿足的最優(yōu)解必滿足1njjjw xC(0)jp 設(shè)設(shè) 是其最優(yōu)解，是其最優(yōu)解，*x要證要證*xx若存在若存在 使使ks*1kx 則至少存在則至少存在 使使 . qs*qqxx取充分小的取充分小的0(滿足滿足: )*1120kkqqwxxw、*,kkkqkqxwwxww則重量增加則重量減少將將

11、 增加增加 減少減少 , ,*kx*,qxkqww此時(shí)此時(shí), ,仍是一個(gè)可行解仍是一個(gè)可行解, ,且目標(biāo)函數(shù)值增加且目標(biāo)函數(shù)值增加 ,()0kkqqwppw矛盾矛盾 .*,1kkksxx對同理可證同理可證*0kks x對又由極大性知：又由極大性知：*sssCxxw因此，因此， 是最優(yōu)解是最優(yōu)解. .x( ()optzC KP易證為最優(yōu)解值Proof :2 2 背包問題的分支定界法背包問題的分支定界法Theorem 2.2設(shè)設(shè)10111ssjjspUpCw11111()ssjssjspUppwCw其中其中 與與 定義同前定義同前. .sC則則的一個(gè)上界為的一個(gè)上界為 ；1()z KP、012ma

12、x(,)UUU2、對背包問題任一實(shí)例，對背包問題任一實(shí)例， .21UU作為上界作為上界U2比比U1更更好好1w1swCsw11sjjCCwswC1111()ssjssjspppwCwswC第七章第七章 背包問題背包問題Proof :1、因?yàn)椤⒁驗(yàn)?KP 中中 xs 不能取分?jǐn)?shù)，不能取分?jǐn)?shù)， 所以，所以，KP 的最優(yōu)解一定是的最優(yōu)解一定是 情形之一情形之一 .01ssxorx當(dāng)當(dāng) ,0sx 由由 Th 2.1 可知，可知， 是此情形的上界是此情形的上界 ； 0U當(dāng)當(dāng) ,1sx 這時(shí)，若這時(shí)，若1211sxxx重量超出重量超出 ,swC而此時(shí)價(jià)值密度值最小的是而此時(shí)價(jià)值密度值最小的是 .11ssp

13、w是此情形的上界是此情形的上界 .1U從而從而 是是 的上界的上界 .012max,()UUUz KP2 2 背包問題的分支定界法背包問題的分支定界法1w1swCsw11sjjCCwswCswC2、要證要證 ，只需，只需證證21UU0111UUand UU是顯然的是顯然的；01UU1111011111ssjjsssjjssssspUpCwpUpCwppCCwwC(KP) 的最優(yōu)解值的最優(yōu)解值11( ()ssoptjjspzC KPpCw1()(*)ssjsjsppwCwC(KP) 當(dāng)當(dāng) 的最優(yōu)解值的最優(yōu)解值1sx 111()(*)ssjsjsppwCw11,sssssppwCww1111()(

14、)ssssjsjsjjsspppwCpwCww11UU從而從而21.UU一般給出的上界越小，計(jì)算量越大，但越容易被剪枝一般給出的上界越小，計(jì)算量越大，但越容易被剪枝 .第七章第七章 背包問題背包問題 書上給出了兩類分支定界法書上給出了兩類分支定界法 (廣探法、深探法廣探法、深探法) ，實(shí)質(zhì)是按什么條件來選結(jié)點(diǎn)進(jìn)行分支，分支是對具有實(shí)質(zhì)是按什么條件來選結(jié)點(diǎn)進(jìn)行分支，分支是對具有最大價(jià)值密度的物品進(jìn)行最大價(jià)值密度的物品進(jìn)行 . 如下介紹的方法是參照確如下介紹的方法是參照確定定 U2 的思想，對關(guān)鍵項(xiàng)進(jìn)行分支的思想，對關(guān)鍵項(xiàng)進(jìn)行分支 .Example 1用分支定界法求如下用分支定界法求如下 KP :

15、770,20,39,37,7,5,1031,10,20,19,4,3,650jjnpwCSolution :可驗(yàn)證可驗(yàn)證7020391031102060K3K2K1K4K091,1,0,0,0,020 x 107u 30 x 31x 39 9702010720u230,0,1,0,0,0,031106xu191,1,0,0,0,019107xu40 x 41x 311,1,0,0,1,1,3105xu41,0,0,1,0,0,0107xu*max1,0,0,1,0,0,0107optxzGo back3 3 背包問題的近似算法背包問題的近似算法 通過前面介紹的通過前面介紹的 C (KP) ，自

16、然想到如下貪婪算法自然想到如下貪婪算法(Greedy Algorithm):111,0ssnxxxx其目標(biāo)函數(shù)值為其目標(biāo)函數(shù)值為 .11sjjp有改進(jìn)的嗎？有改進(jìn)的嗎？GA0step 10001xwkstep 210kjjkjw xwC若若 ,則則 ，1kx 否則否則 ；0kx step 3若若 則結(jié)束則結(jié)束;,kn:1,kk否則否則2 .step轉(zhuǎn)轉(zhuǎn)GA0是近似是近似算法嗎？算法嗎？第七章第七章 背包問題背包問題構(gòu)造例子構(gòu)造例子 I :11222,1,1,.npwpkwkCk 按上述算法，得按上述算法，得：0121,0,( )1;GAxxzI 為充分小的正數(shù)為充分小的正數(shù) .而顯然最優(yōu)解為而

17、顯然最優(yōu)解為：120,1,( ).optxxzIk0( )10()( )GAoptzIkzIk 說明說明 GA0 的絕對性能比不會(huì)大于任意給定的正數(shù)的絕對性能比不會(huì)大于任意給定的正數(shù),所以，它不能作為近似解所以，它不能作為近似解 . 但稍加改進(jìn)，就可得到一但稍加改進(jìn)，就可得到一個(gè)絕對性能比為常數(shù)的較好的近似算法個(gè)絕對性能比為常數(shù)的較好的近似算法 .3 3 背包問題的近似算法背包問題的近似算法GA1step 1step 2求解求解 C(KP)，得關(guān)鍵項(xiàng)記為，得關(guān)鍵項(xiàng)記為 s ;取取 作為近似解值作為近似解值 .11max,sjsjpp即若即若 ，則，則11sjsjpp111,0ssnxxxx否則

18、否則1110,1ssnsxxxxxExample 243,7,17,20 ,1,3,8,1011jjnpwCSolution :顯然，物品顯然，物品3 為關(guān)鍵項(xiàng)（即為關(guān)鍵項(xiàng)（即 s = 3）易驗(yàn)證易驗(yàn)證37172013810123710,pp而而317p 近似解為近似解為112430,1;17GAxxxxz有改進(jìn)的嗎？有改進(jìn)的嗎？用用 GA1 求如下求如下 KP :第七章第七章 背包問題背包問題GA2step 1求解求解 C(KP)，得關(guān)鍵項(xiàng)記為，得關(guān)鍵項(xiàng)記為 s ;step 2令令 maxijjpp若若11sjijpp111,0ssnxxxx則則否則否則1110,1iinixxxxxExam

19、ple 343,7,17,20 ,1,3,8,1011jjnpwC用用 GA2 求如下求如下 KP :Solution :123710,pp而而 4max20jjpp212340,1;20GAxxxxz 近似解為近似解為Theorem 2.311.2GARproof11( )sup1( )GAGAIoptzIRrrzI3 3 背包問題的近似算法背包問題的近似算法Theorem 2.421.2GAR證明與證明與 Th 2.3 的類似的類似 .對對Ex . 343,7,17,20 ,1,3,8,1011jjnpwC考慮對考慮對 GA2 進(jìn)行修改，進(jìn)一步可取進(jìn)行修改，進(jìn)一步可取14231,0 xxx

20、x則則23z 這在實(shí)際計(jì)算中是會(huì)有好處的這在實(shí)際計(jì)算中是會(huì)有好處的 . 但絕對性能比不但絕對性能比不會(huì)改進(jìn)會(huì)改進(jìn) .Go onTheorem 2.3 的證明的證明Proof :先證先證再說明不可改進(jìn)再說明不可改進(jìn)112GAR由由 s 的定義知：的定義知： 對于任意實(shí)例對于任意實(shí)例 I11( )soptjsjzIpp111111( )max,()2ssGAjsjsjjzIpppp又又因此因此，1( )1( )2GAoptzIzI從而從而112GAR取實(shí)例取實(shí)例 I：113,1,1,npw 為充分小的正數(shù)為充分小的正數(shù) .2323,2ppwwkCk1123( )1,1,0GAzIkxxx 123(

21、 )2 ,0,1optzIkxxx1( )11()( )22GAoptzIkkzIk則則112GAR從而從而112GAR第七章第七章 背包問題背包問題3 3 背包問題的近似算法背包問題的近似算法 已知已知 GA0 對解對解 0-1 背包問題效果很差，但在一般背背包問題效果很差，但在一般背包問題中卻是可以的包問題中卻是可以的 .設(shè)設(shè) 11max. .0 ,1njjjnjjjjzp xstw xCxzjn顯然，顯然，121,0nCxxxw是一個(gè)可行解是一個(gè)可行解 .011GACzpw通過求解通過求解 C(KP) 得得11( )optCzIpw松弛問題的最優(yōu)解值松弛問題的最優(yōu)解值01111( )1(

22、 )21GAoptCCzIwwCzICww012GAR進(jìn)一步可證進(jìn)一步可證012GAR1212:3 ,220,IpkpkkkwwCk第七章第七章 背包問題背包問題1975年年 Sahni 給出一個(gè)多項(xiàng)式時(shí)間近似算法給出一個(gè)多項(xiàng)式時(shí)間近似算法 .算法算法Sk :step 1對任意滿足對任意滿足1,2,MNnMk且且 的子集的子集 M ， ii MwC先將先將 M 中的物品放入包內(nèi)中的物品放入包內(nèi),然后用算法然后用算法 GA1 或或 GA2 求解一個(gè)如下定義的求解一個(gè)如下定義的 KP ：物品集為物品集為 NM ，包容量為包容量為 ，ii MCw將得到的解與將得到的解與M 的并作為原問題的近似解的并

23、作為原問題的近似解 .step 2取上述所有不同解中最好一個(gè)作為輸出取上述所有不同解中最好一個(gè)作為輸出 .Theorem 2.511kSRk 計(jì)算復(fù)雜計(jì)算復(fù)雜性性1()kO kn證略證略 參見其他資料參見其他資料3 3 背包問題的近似算法背包問題的近似算法Theorem 2.6 如果如果 ，則背包問題不存在滿足下，則背包問題不存在滿足下述性質(zhì)的多項(xiàng)式時(shí)間算法述性質(zhì)的多項(xiàng)式時(shí)間算法 A :PNP 存在固定的正整數(shù)存在固定的正整數(shù) K 使得對任意的實(shí)例使得對任意的實(shí)例 I 有有( )( ).AoptzIzIKProof : 用反證法，假定存在，則可證明算法用反證法，假定存在，則可證明算法 A 可在

24、多項(xiàng)式內(nèi)可在多項(xiàng)式內(nèi)精確地解精確地解 KP，但，但 KP 是是NP-C 的，這與的，這與 矛盾矛盾 .PNP 給定給定 KP 任一實(shí)例任一實(shí)例 I ，將物品，將物品 j 的價(jià)值換成的價(jià)值換成 (K+1)pj, 而重量而重量wj 不變，包的容量不變，由此得到一個(gè)新的實(shí)例不變，包的容量不變，由此得到一個(gè)新的實(shí)例 I . 顯然由顯然由 I 構(gòu)造構(gòu)造 I 是在多項(xiàng)式時(shí)間內(nèi)完成的是在多項(xiàng)式時(shí)間內(nèi)完成的 . 用用 A 解解 I 得到的解，也是得到的解，也是 I的一個(gè)可行解的一個(gè)可行解 . 算法算法A: I I, 用算法用算法 A 解解I,得到得到 I 的可行解的可行解 . 算法算法 A是多項(xiàng)是多項(xiàng)式時(shí)間算

25、法式時(shí)間算法 由于由于 I 與與 I 有相同的可行解集，有相同的可行解集，I 的任一可行解值是的任一可行解值是 I 的的同一可行解值的同一可行解值的 （K+1）倍，所以）倍，所以1( )( )( )( ) .1AoptAoptzIzIzIzIK( )( ),AoptzIzIK由假設(shè)知( )( )1.1AoptKzIzIK所以 由于由于 KP 任一可行解值為正整數(shù)，因此任一可行解值為正整數(shù)，因此 z A (I) = zopt (I)，這說明，這說明 A 總能得到實(shí)例總能得到實(shí)例 I 的最優(yōu)的最優(yōu)解，正是所需要的矛盾解，正是所需要的矛盾.Go back一、有界背包問題一、有界背包問題0-1 背包問

26、題背包問題：01 ;jxor一般背包問題一般背包問題： 0;jxz（無界背包問題）（無界背包問題）有界背包問題有界背包問題：0jjjxbb為給定的正整數(shù)為給定的正整數(shù) .( Bounded Knapsack Problem )顯然，顯然，GKP 可化為可化為 BKP，只需令，只需令jjCbwBKP 可化為等價(jià)的可化為等價(jià)的 0-1 KP思想思想：任一整數(shù)可用任一整數(shù)可用 0 , 1 變量來表示，如變量來表示，如 非負(fù)整數(shù)非負(fù)整數(shù)16x231234222xxxxx如如 1312341,0,1,1xxxx第七章第七章 背包問題背包問題Theorem 2.7記記11min,jsiijjijsjbwCCCb w則則（1） 是是 BKP 的一個(gè)上界的一個(gè)上界 ；111s