用動態規劃法和貪心法解決背包問題

算法與語言

用動態規劃法和貪心法解決背包問題

唐

敏１，劉冠蓉１，鄧國強

２

（１．武漢理工大學計算機科學與技術學院，湖北武漢４３００７０；

２．武漢理工大學理學院，湖北武漢４３００７０）

摘要：０－１背包問題和背包問題是一類經典的ＮＰ困難問題。采用動態規劃法和貪心法對該問題進行求

解，分析和比較這兩種算法在求解同一問題時的差異。

關鍵詞：背包問題；０－１背包問題；動態規劃法；貪心法中圖分類號：ＴＰ３１２

文獻標識碼：Ａ

文章編號：１６７２－７８００（２００７）０３－０１１１－０３

１０－１背包問題與背包問題

１．１０－１背包問題

給定ｎ個重量為（ｗ１，ｗ２，∧，ｖｎ）價值為（ｖ１，ｖ２，∧，ｖｎ）的物品和一個承重量為Ｗ的背包，求這些物品中最有價值的一個子集，并且要能夠裝到背包中。

在選擇裝入背包的物品ｉ時，對每種物品只有兩種選擇，即裝入背包或不裝入背包。不能將物品裝入背包多次，也不能只裝入部分的物品。在這里假設所有的重量和背包的承重量都是正整數。

選擇物品裝入背包時，可以選擇物品的一部分，而不一定要全部裝入背包。

２ｎ，所以不論生成獨立子集的效率有多高，

窮舉查找都會導致一個-（２ｎ）的算法。即對于任何輸入都非常缺乏效率的算法。這就是所謂的困難問題，目前沒有已知的，效率可以用多項式來表示的算法。

表２窮舉過程和實例的解子

集

總重量

總價值

１．４背包問題的形式化描述

給定Ｗ＞０，Ｗｉ＞０，ｖｉ＞０，１≤ｉ≤ｎ，要求找出ｎ元０－１向量（ｘ１，ｘ２，∧，ｘｎ），０≤ｘｉ≤１，１≤

ｎ

ｎ

ｉ≤ｎ使得%ｗｉｘｉ≤Ｗ，而且%ｖｉｘｉ≤Ｗ達

ｉ＝１

ｉ＝１

到最大。

２０－１背包問題的一個小規模的實

例

表１

物品

重量

價值

⊙｛１｝｛２｝｛３｝｛４｝｛１，２｝｛１，３｝｛１，４｝www.ipr-jzsc.com｛２，３｝｛２，４｝｛３，４｝｛１，２，３｝｛１，２，４｝｛１，３，４｝｛２，３，４｝｛１，２，３，４｝

大價值為３７美元。

０２１３２３５４４３５６５７６８

０１２１０２０１５２２３２２３０２５３５

不可行

１．２０－１背包問題的形式化描述

給定Ｗ＞０，Ｗｉ＞０，ｖｉ＞０，１≤ｉ≤ｎ，要求找出ｎ元０－１向量（ｘ１，ｘ２，∧，ｘｎ），ｘｉ∈｛０，１｝，

ｎ

ｎ

１２３４

承重量Ｗ＝５

２１３２

１２美元１０美元２０美元１５美元

１≤ｉ≤ｎ使得%ｗｉｘｉ≤Ｗ，而且&ｖｉｘｉ達

ｉ＝１

ｉ＝１

到最大。因此，０－１背包問題是一個特殊的整數規劃問題。

ｎ

考慮下面數據給出的實例：

在０－１背包問題中，采用窮舉查找需要考慮給定的ｎ個物品集合的所有子集，為了找出可行的子集（也就是說，總重量不超過背包承重能力的子集）。要計算出每個子集的總重量，然后在它們中間找到價值最大的子集。

因為一個ｎ元素集合的子集數量是

ｍａｘ&ｖｉｘｉ

ｉ＝１

(

****)ｉ****+

３７

不可行不可行不可行

&ｗｘ≤Ｗ

＝１

ｉｉ

ｎ

ｘｉ∈｛０，１｝，１≤ｉ≤ｎ

１．３背包問題最優解為｛物品１，物品２，物品４｝，最

與０－１背包問題類似，所不同的是在

作者簡介：唐敏（１９８０－），女，廣西桂林人，武漢理工大學助教、碩士，研究方向為智能計算；劉冠蓉，男，武漢理工大學教授，主要研究領域為智能計算、數

據挖掘；鄧國強（１９７９－），男，武漢理工大學助教、碩士，研究方向為演化計算。

月號１１１

算法與語言

３動態規劃法

表４動態規劃算法解背包問題實例次大，且能夠裝入背包，此時背包已滿。這時得到的總價值為３５，它是一個次優解。因此，按物品效益值的非遞增次序裝包不一定能得到最優解。

為什么每一步使目標函數值獲得當前最大增值的貪心策略卻沒有獲得最優解呢？原因在于：雖然每一步獲得了效益值的極大增長，但背包容量消耗太快。

（２）以容量為度量標準。物品２（承重

３．１動態規劃法的基本思想

動態規劃法是一種強有力的算法設計技術，它被廣泛用于求解組合最優化問題。這種技術采用自底向上的方式遞推求值，將待求解的問題分解成若干個子問題，先求解子問題，并把子問題的解存儲起來以便以后用來計算所需要求的解。

３．２遞推公式

為了設計一種動態規劃算法，需要推導出一個遞推關系，用較小實例的解的形式來表示背包問題的實例的解。

解決０－１背包問題的遞推式如下：

優子集的一部分。因為Ｖ［２，３］≠Ｖ［１，３］，物品２是最優選擇的一部分，這個最優子集用元素Ｖ［１，３－１］來指定余下的組成部分。同樣道理，因為Ｖ［１，２］≠Ｖ［０，２］，物品１是最優解｛物品１，物品２，物品４｝的最后一個部分。

該算法的時間效率和空間效率都屬于!（ｎＷ）。用來求最優解的具體組成的

（１）

時間效率屬于Ｏ（ｎ＋Ｗ）。

量＝１，價值＝１０美元）承重量最小的首先裝包，剩下４個承重量，再裝入物品４（承重量＝２，價值＝１５美元），此時剩下２個承重量，裝入物品１（承重量＝２，價值＝１２美元），背包已滿，此時得到的總價值為３７美元。此時得到了該問題的最優解。

（３）貪心法小結。從用貪心法解決０－１背包問題可以看出，采用不同的貪心策略對求解問題的結果也有所不同。所以，當我們在使用貪心法時，必須證明該算法可以導致問題的最優解。

和在動態規劃算法的情況中一樣，貪心法通常用來求解最優化問題，即量的最大化或最小化。然而，貪心法不像動態規劃算法，它通常包含一個用以尋找局部最優解的迭代過程。在某些實例中，這些局部最優解轉變成了全局最優解，而在另外一些情況下，則無法找到最優解。

貪心法在少量計算的基礎上作出了正確猜想，而不急于考慮以后的情況，這樣，它一步步地來構筑解，每一步均是建立在局部最優解的基礎之上，而每一步又都擴大了部分解的規模，做出的選擇產生最大效益而又保持可行性。因為每一步的工作很少且基于少量信息，所得算法特別有效。

Ｖ［ｉ，ｊ］＝

ｍａｘ｛Ｖ［ｉ－１，ｊ］，ｖｉ＋Ｖ［ｉ－１，ｊ－ｗｉ］｝如果ｊ－ｗｉ≥０

Ｖ［ｉ－１，ｊ］，如果ｊ－ｗｉ＜０

定義初始條件：當時ｊ≥０時，Ｖ［０，ｊ］＝０；當ｉ≥０時，Ｖ［ｉ，０］＝０

（２）

我們的目標是求Ｖ［ｎ，ｗ］，即一個給定

４

４．１

貪心法

貪心法的基本思想

貪心法總是作出在當前看來最好的選擇，也就是說貪心法并不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。雖然貪心法不能對所有的問題都得到整體最優解，但對于許多問題它能產生整體最優解。在一些情況下，即使貪心法不能得到整體最優解，其最終結果卻是最優解的很好近似。

貪心法是一種最直接的設計技術，它能應用于求解多種問題。這類問題的一般特征是有ｎ個輸入以及一組約束條件，滿足約束條件的任一輸入的子集稱為可行解，其可行解由這ｎ個輸入的某個子集組成。顯然，滿足約束條件的子集可能不止一個，因此，可行解是不唯一的。為了衡量可行解的優劣，事先也給出一定的標準。

物品中能夠放進承重量為Ｗ的背包的子集的最大總價值，以及最優子集本身。

３．３動態規劃表的設計

當ｉ，ｊ＞０時，為了計算第ｉ行第ｊ列的單元格Ｖ［ｉ，ｊ］，我們拿前一行同一列的單元格與ｖｉ加上前一行左邊ｗｉ列的單元格的和作比較，計算出兩者的較大值。這個表格可以一行一行地填，也可以一列一列地填。

表３動態規劃表

５

５．１

動態規劃法和貪心法的分析

動態規劃法的設計原理

考慮表１給出的實例，表４給出了用公式（１）（２）填寫的動態規劃表。

這些標準一般以函數的形式給出，這些函數稱為目標函數。可使目標函數達到極值（極大或者極�。┑目尚薪猓�稱為最優解。對于其中的某些問題，可用貪心法求解。

動態規劃是基于遞歸的技術，遞歸算法通常擁有十分簡單的歸納證明。算法設計中一個十分重要的原理，稱為最優化原理：給定一個最優的決策序列，每個子系列自身必須是最優的決策序列。

在動態規劃算法中，每步所做出的選擇往往依賴于相關子問題的解。因而，只有在解出相關子問題后，才能作出選擇。

動態規劃法通常以自底向上的方式

３．４最優解和最優子集

因此，最大總價值為Ｖ［４，５］＝３７美元�？梢酝ㄟ^回溯這個表格單元的計算過程來求得最優子集的組成元素。因為Ｖ［４，５］

４．２用貪心法解０－１背包問題（仍引用表

１的實例）

（１）以目標函數為度量標準進行裝包。物品３（承重量＝３，價值＝２０美元）效益最大的首先裝包，剩下２個承重量，再裝入物品４（承重量＝２，價值＝１５美元）效益

≠Ｖ［３，５］，物品４以及填滿背包余下５－２＝３個單位承重量的一個最優子集都包括

在最優解中。而后者是由元素Ｖ［３，３］來表示的。因為Ｖ［３，３］＝Ｖ［２，３］，物品３不是最

算法與語言

解各個子問題。質。問題的最優子結構性質是該問題可用入背包。依此策略一直進行下去，直到背５．２貪心法的基本要素

動態規劃算法或貪心法求解的關鍵特征。

包裝滿為止。

５．２．１貪心選擇性質

５．３動態規劃法與貪心法的差異

對于０－１背包問題，貪心選擇之所以所謂貪心選擇性質是指所求問題的

動態規劃法和貪心法都要求問題具不能得到最優解是因為在這種情況下，它整體最優解可以通過一系列局部最優的有最優子結構性質，這是兩類算法的一個無法保證最終能將背包裝滿，部分閑置的選擇，即貪心選擇來達到。這是貪心法可共同點。但是，對于具有最優子結構的問背包空間使每單位背包空間的價值降低行的第一個基本要素，也是貪心法與動態題應該選用動態規劃法還是貪心法求解？了。事實上，在考慮０－１背包問題時，應比規劃算法的主要區別。

是否能用動態規劃算法求解的問題也能較選擇該物品和不選擇該物品所導致的貪心法所做出的貪心選擇可以依賴用貪心法求解？

最終方案，然后再做出最好選擇。由此就于以往所做過的選擇，但決不依賴于將來０－１背包問題與背包問題這兩類問

導出許多互相重疊的子問題。這正是該問所做的選擇，也不依賴于子問題的解。

題都具有最優子結構性質。對于０－１背包題可用動態規劃算法求解的另一重要特貪心法通常以自頂向下的方式進行，問題，設Ａ是能夠裝入容量為Ｗ的背包征。實際上也是如此，動態規劃算法的確以迭代的方式做出相繼的貪心選擇，每做價值的物品集合，則Ａｊ＝Ａ－｛ｊ｝是ｎ－１個物可以有效地解０－１背包問題。

出一次貪心選擇就將所求問題簡化為規品１，２，∧，ｊ－１，ｊ＋１，∧，ｎ可裝入容量為Ｗ－ｗｊ動態規劃法和貪心法的基本區別在模更小的子問題。

的背包的具有最大價值的物品集合。對于于，貪心法僅產生一個判定序列，而動態對于一個具體問題，要確定它是否具背包問題，類似地，若它的一個最優解包規劃法可能產生許多判定序列，但是按照有貪心選擇性質，必須證明每一步所作出含物品ｊ，則從該最優解中拿出所含的物最優原理，包含非局部最優的部分序列的的貪心選擇最終導致問題的整體最優解。品ｊ的那部分重量ｗ，剩下的將是ｎ－１個結果肯定不可能是最優的，所以不予考首先考察問題的一個整體最優解，并證明原重物品１，２，∧，ｊ－１，ｊ＋１，∧，ｎ以及重為ｗｊ－

慮。設計貪心法的困難部分就是要證明該可修改這個最優解，使其以貪心選擇開ｗ的物品ｊ中可裝入容量為Ｗ－ｗ的背包

算法確實是求解了它所需要解決的問題。

始。做出貪心選擇后，原問題簡化為規模且具有最大價值的物品。

參考文獻：

更小的類似子問題。然后，用數學歸納法雖然這兩個問題極為相似，但背包問證明，通過每一步做貪心選擇，最終可得題可以用貪心法求解，而０－１背包問題卻［１］王曉東．算法設計與分析［Ｍ］．北京：清華大

到問題的整體最優解。其中，證明貪心選不能用貪心法求解。用貪心法解背包問題學出版社，２００３．

擇后的問題簡化為規模更小的類似子問的基本步驟是：首先計算每種物品單位重［２］宋文，吳晟，杜亞軍．算法設計與分析［Ｍ］．

重慶：重慶大學出版社，２００２．

題的關鍵在于利用該問題的最優子結構量的價值ｖｉ／ｗｉ，然后，依貪心選擇策略，將［３］ＡｎａｎｙＬｅｖｉｔｉｎ．算法設計與分析基礎［Ｍ］．北

性質。

盡可能多的單位重量價值最高的物品裝京：清華大學出版社，２００４．

５．２．２最優子結構性質

入背包。若將這種物品全部裝入背包后，［４］盧開澄．計算機算法導引—設計與分析［Ｍ］．

當一個問題的最優解包含其子問題

背包內的物品總重量未超過Ｗ，則選擇單北京：清華大學出版社，２００３．

的最優解時，稱此問題具有最優子結構性

位重量價值次高的物品并盡可能多地裝

（責任編輯：曙光）

Ｓｏｌｖｉｎｇ０－１ＫｎａｐｓａｃｋＰｒｏｂｌｅｍｓｂｙＤｙｎａｍｉｃＰｒｏｇｒａｍｍｉｎｇＭｅｔｈｏｄａｎｄＧｒｅｅｄｙＭｅｔｈｏｄ

ＴＡＮＧＭｉｎ，ＬＩＵＧｕａｎ－ｒｏｎｇ１，ＤＥＮＧＧｕｏ－ｑｉａｎｇ２

（１．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＷｕｈａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ４３００７０，Ｃｈｉｎａ；

２．ＳｃｈｏｏｌｏｆＮａｔｕｒｅＳｃｉｅｎｃｅ，ＷｕｈａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｄｏｇｙ，Ｗｕｈａｎ４３００７０，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：０－１ｋｎａｐｓａｃｋｐｒｏｂｌｅｍｓａｎｄｋｎａｐｓａｃｋｐｒｏｂｌｅｍｓａｒｅａｃｌａｓｓｉｃａｌＮＰｈａｒｄｐｒｏｂｌｅｍｓ．Ｔｈｉｓｐａｐｅｒａｄｏｐｔｓｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇｍｅｔｈｏｄａｎｄｇｒｅｅｄｙｍｅｔｈｏｄｔｏｓｏｌｖｅｓｕｃｈｐｒｏｂｌｅｍｓ，ｔｈｅｎａｎａｌｙｚｅｓａｎｄｃｏｍｐａｒｅｓｔｈｅｄｉｆｆｅｒｅｎｃｅｓｏｆｔｗｏａｌｇｏ－ｒｉｔｈｍｓ．

Ｋｅｙｗｏｒｄｓ：０－１ｋｎａｐｓａｃｋｐｒｏｂｌｅｍｓ；ｋｎａｐｓａｃｋｐｒｏｂｌｅｍｓ；ｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇｍｅｔｈｏｄ；ｇｒｅｅｄｙｍｅｔｈｏｄ

月號１１３

【用動態規劃法和貪心法解決背包問題】相關文章：

用智慧解決問題作文08-10

教案：用除法解決問題04-24

金岳霖對歸納問題的表述和邏輯解決05-02

用發展的辦法解決前進中的問題05-02

《用數學解決問題》教案修改04-25

《用除法解決實際問題》教案03-04

用比例解決問題教學反思04-22

用連乘解決問題教學反思04-22

用新理念解決政工新問題04-26

8和9解決問題課后反思04-12