1、第七章 背包問題,組合優(yōu)化理論,Combinatorial Optimization Theory,第七章 背包問題,1 背包問題的描述,2 背包問題的分支定界法,3 背包問題的近似算法,4 0-1背包問題的一些相關(guān)問題,第七章 背包問題,背包問題 ( Knapsack Problem ) 是一個(gè)有著廣泛應(yīng) 用的組合優(yōu)化問題，它不僅在投資決策、裝載、庫存等 方面有應(yīng)用，而且常以子問題形式出現(xiàn)在大規(guī)模優(yōu)化問 題中，它的理論與算法具有一定的代表性.,1 背包問題的描述,背包問題的一般描述為：設(shè)有物品集 是一個(gè)準(zhǔn)備放入容量為 的背包中的 n 項(xiàng)物品的集 合.,物品 的重量為 價(jià)值為,如何選擇 U 中

2、的一些物品裝入背包，使這些物品的 總重量不超過 C ，且使總價(jià)值達(dá)到最大？,1 背包問題的描述,背包問題的數(shù)學(xué)模型：,重量,價(jià)值,容量,因?yàn)闆Q策變量 ,所以也稱 0-1 背包問題.,一般背包問題:,( General Knapsack Problem ),第七章 背包問題,為討論方便，總可假定（相當(dāng)于標(biāo)準(zhǔn)化）：,即按價(jià)值密度從大到小排列.,實(shí)際問題并非滿足,1 背包問題的描述,對(duì) 4 只需 O(nln n)次運(yùn)算即可；,對(duì) 3 若 ，最優(yōu)解為 ;,對(duì) 2 若 ，則最優(yōu)解中 事先可去掉;,對(duì) 1 分三種情況討論:,(1) 若 且,令,此時(shí)，最優(yōu)解中,所以，該物品事先可去掉;,(2) 若 且,令,

3、此時(shí)，最優(yōu)解中,所以，該物品事先可去掉;,容量取,第七章 背包問題,(3) 若 且,令,只需在模型中，令 ，則系數(shù)即為大于零了.,綜上，對(duì)不滿足（1）、（2）、（3）的假定，可 作如下處理，使之滿足：,對(duì) 令,對(duì) 令,則原問題化為：,1 背包問題的描述,如果在（KP）中，令,令,該問題的實(shí)際意義 是求不放在包中的物 品的價(jià)值和最小 .,模型的意義,Go back,第七章 背包問題,2 背包問題的分支定界法,分支定界法 ( Branch and Bound Method ) 的基本 思想在運(yùn)籌學(xué)課程中已介紹，它的重要在于它提出了一 類新的思路（隱枚舉法），使得許多原來不好解決的問 題有了解決的可

4、能性。（具有普適性）, 確定問題（子問題）的最優(yōu)值的界,極大（?。┗瘑栴} 上（下）界,通常是通過求解松弛問題，用松弛問題的解作為界,Note : 松弛問題選擇的原則,1、松弛問題要與原問題的最優(yōu)值盡量接近；,2、松弛問題要盡量容易解 .,這兩個(gè)原則不易統(tǒng)一，所以可選擇不同的松弛問題,2 背包問題的分支定界法, 劃分方法的選擇,原則是希望分出來的子問題容易被查清，可加快計(jì)算., 選哪個(gè)活問題先檢查,1、先檢查最大上界（極大化問題）的活問題,優(yōu)點(diǎn)：檢查子問題較其他規(guī)則為少；,缺點(diǎn)：計(jì)算機(jī)儲(chǔ)存量較大 .,2、先檢查最新產(chǎn)生的最大上界的活問題,優(yōu)點(diǎn)：計(jì)算機(jī)儲(chǔ)存量較少 ；,缺點(diǎn)：需要更多的分支運(yùn)算 .,

5、選擇的不同，提供了發(fā)揮的余地,第七章 背包問題,考慮 KP 的松弛問題 ：,C(KP)如何求解？,思路：將物品按價(jià)值密度從大到小的順序放入包內(nèi), ,記, 關(guān)鍵項(xiàng),第一個(gè)放不下的 物品的序號(hào),?,Theorem 2.1,2 背包問題的分支定界法,C(KP) 最優(yōu)解為,其中,最優(yōu)解值為,proof,顯然， ，,由于 的整數(shù)性，,得到 z ( KP ) 的一個(gè)上界：,表示不超過 的最大整數(shù).,Go on,Go back,第七章 背包問題,Theorem 2.1 的證明,顯然 C(KP) 的最優(yōu)解必滿足,設(shè) 是其最優(yōu)解，,要證,若存在 使,則至少存在 使 .,取充分小的,(滿足: ),將 增加 減少

6、,此時(shí),仍是一個(gè)可行解,且目標(biāo)函數(shù)值增加 ,矛盾 .,同理可證,又由極大性知：,因此， 是最優(yōu)解.,Proof :,2 背包問題的分支定界法,Theorem 2.2,設(shè),其中 與 定義同前.,則,的一個(gè)上界為 ；,2、對(duì)背包問題任一實(shí)例， .,作為上界U2比U1更好,第七章 背包問題,Proof :,1、因?yàn)?KP 中 xs 不能取分?jǐn)?shù)，,所以，KP 的最優(yōu)解一定是 情形之一 .,當(dāng) ,由 Th 2.1 可知， 是此情形的上界 ；,當(dāng) ,這時(shí)，若,重量超出 ,而此時(shí)價(jià)值密度值最小的是 .,是此情形的上界 .,從而 是 的上界 .,2 背包問題的分支定界法,2、,要證 ，只需證,是顯然的；,C(

7、KP) 的最優(yōu)解值,C(KP) 當(dāng) 的最優(yōu)解值,從而,一般給出的上界越小，計(jì)算量越大，但越容易被剪枝 .,第七章 背包問題,書上給出了兩類分支定界法 (廣探法、深探法) ， 實(shí)質(zhì)是按什么條件來選結(jié)點(diǎn)進(jìn)行分支，分支是對(duì)具有 最大價(jià)值密度的物品進(jìn)行 . 如下介紹的方法是參照確 定 U2 的思想，對(duì)關(guān)鍵項(xiàng)進(jìn)行分支 .,Example 1,用分支定界法求如下 KP :,Solution :,可驗(yàn)證,*,*,*,Go back,3 背包問題的近似算法,3 背包問題的近似算法,通過前面介紹的 C (KP) ，自然想到如下貪婪算法 (Greedy Algorithm):,其目標(biāo)函數(shù)值為 .,有改進(jìn)的嗎？,G

8、A0,step 1,step 2,若 ,則 ，,否則 ；,step 3,若 則結(jié)束;,否則,轉(zhuǎn),GA0是近似 算法嗎？,第七章 背包問題,構(gòu)造例子 I :,按上述算法，得：,為充分小的正數(shù) .,而顯然最優(yōu)解為：,說明 GA0 的絕對(duì)性能比不會(huì)大于任意給定的正數(shù), 所以，它不能作為近似解 . 但稍加改進(jìn)，就可得到一 個(gè)絕對(duì)性能比為常數(shù)的較好的近似算法 .,3 背包問題的近似算法,GA1,step 1,step 2,求解 C(KP)，得關(guān)鍵項(xiàng)記為 s ;,取 作為近似解值 .,即若 ，則,否則,Example 2,Solution :,顯然，物品3 為關(guān)鍵項(xiàng)（即 s = 3）,易驗(yàn)證,而,近似解為

9、,有改進(jìn)的嗎？,用 GA1 求如下 KP :,第七章 背包問題,GA2,step 1,求解 C(KP)，得關(guān)鍵項(xiàng)記為 s ;,step 2,令,若,則,否則,Example 3,用 GA2 求如下 KP :,Solution :,而,近似解為,Theorem 2.3,proof,3 背包問題的近似算法,Theorem 2.4,證明與 Th 2.3 的類似 .,對(duì)Ex . 3,考慮對(duì) GA2 進(jìn)行修改，進(jìn)一步可取,則,這在實(shí)際計(jì)算中是會(huì)有好處的 . 但絕對(duì)性能比不 會(huì)改進(jìn) .,Go on,Theorem 2.3 的證明,Proof :,先證 再說明不可改進(jìn),由 s 的定義知：,對(duì)于任意實(shí)例 I,

10、又,因此，,從而,取實(shí)例 I：,為充分小的正數(shù) .,則,從而,第七章 背包問題,3 背包問題的近似算法,已知 GA0 對(duì)解 0-1 背包問題效果很差，但在一般背 包問題中卻是可以的 .,設(shè),顯然，,是一個(gè)可行解 .,通過求解 C(KP) 得,松弛問題的最優(yōu)解值,進(jìn)一步可證,第七章 背包問題,1975年 Sahni 給出一個(gè)多項(xiàng)式時(shí)間近似算法 .,算法Sk :,step 1,對(duì)任意滿足,且 的子集 M ，,先將 M 中的物品放入包內(nèi),然后用算法 GA1 或 GA2 求解一個(gè)如下定義的 KP ：,物品集為 NM ，包容量為 ，,將得到的解與,M 的并作為原問題的近似解 .,step 2,取上述所有

11、不同解中最好一個(gè)作為輸出 .,Theorem 2.5,計(jì)算復(fù)雜性,證略 參見教材 p99,3 背包問題的近似算法,Theorem 2.6,如果 ，則背包問題不存在滿足下 述性質(zhì)的多項(xiàng)式時(shí)間算法 A :,存在固定的正整數(shù) K 使得對(duì)任意的實(shí)例 I 有,Proof :,用反證法，假定存在，則可證明算法 A 可在多項(xiàng)式內(nèi) 精確地解 KP，但 KP 是NP-C 的，這與 矛盾 .,給定 KP 任一實(shí)例 I ，將物品 j 的價(jià)值換成 (K+1)pj, 而重量 wj 不變，包的容量不變，由此得到一個(gè)新的實(shí)例 I . 顯然由 I 構(gòu)造 I 是在多項(xiàng)式時(shí)間內(nèi)完成的 . 用 A 解 I 得到的解，也是 I 的一

12、個(gè)可行解 .,算法 A是多項(xiàng)式時(shí)間算法,由于 I 與 I 有相同的可行解集，I 的任一可行解值是 I 的 同一可行解值的 （K+1）倍，所以,由于 KP 任一可行解值為正整數(shù)，因此 z A (I) = zopt (I)，這說明 A 總能得到實(shí)例 I 的最優(yōu) 解，正是所需要的矛盾.,Go back,4 0-1背包問題的一些相關(guān)問題,一、有界背包問題,0-1 背包問題：,一般背包問題：,（無界背包問題）,有界背包問題：,為給定的正整數(shù) .,( Bounded Knapsack Problem ),顯然，GKP 可化為 BKP，只需令,BKP 可化為等價(jià)的 0-1 KP,思想：,任一整數(shù)可用 0 , 1 變量來表示，如 非負(fù)整數(shù),如 13,第七章 背包問題,Theorem 2.7,記,則,（1） 是 BKP 的一個(gè)上界 ；,（2）取,得到一個(gè)可行解，將此解的值與 bs ps 的值比較, 取大者為輸出 .,該算法的絕對(duì)性能比 ,計(jì)算復(fù)雜性為,與前面討論一樣，總可假定 都是正整數(shù);,4 0-1背包問題的一些相關(guān)問題,二、子集和問題,在組合優(yōu)化問題中，很多問題是相通的，參數(shù)稍作 修正，可能就是另一個(gè)問題 .,即,稱為子集和問題,Subset Sum Problem,SSP 是 0-1KP 的特殊情形，所以原方法皆可用. 但 因其特殊，它