- 相關(guān)推薦
用動態(tài)規(guī)劃法和貪心法解決背包問題
算法與語言
用動態(tài)規(guī)劃法和貪心法解決背包問題
唐
敏１，劉冠蓉１，鄧國強
２
（１．武漢理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院，湖北武漢４３００７０；
２．武漢理工大學(xué)理學(xué)院，湖北武漢４３００７０）
摘要：０－１背包問題和背包問題是一類經(jīng)典的ＮＰ困難問題。采用動態(tài)規(guī)劃法和貪心法對該問題進(jìn)行求
解，分析和比較這兩種算法在求解同一問題時的差異。
關(guān)鍵詞：背包問題；０－１背包問題；動態(tài)規(guī)劃法；貪心法中圖分類號：ＴＰ３１２
文獻(xiàn)標(biāo)識碼：Ａ
文章編號：１６７２－７８００（２００７）０３－０１１１－０３
１０－１背包問題與背包問題
１．１０－１背包問題
給定ｎ個重量為（ｗ１，ｗ２，∧，ｖｎ）價值為（ｖ１，ｖ２，∧，ｖｎ）的物品和一個承重量為Ｗ的背包，求這些物品中最有價值的一個子集，并且要能夠裝到背包中。
在選擇裝入背包的物品ｉ時，對每種物品只有兩種選擇，即裝入背包或不裝入背包。不能將物品裝入背包多次，也不能只裝入部分的物品。在這里假設(shè)所有的重量和背包的承重量都是正整數(shù)。
選擇物品裝入背包時，可以選擇物品的一部分，而不一定要全部裝入背包。
２ｎ，所以不論生成獨立子集的效率有多高，
窮舉查找都會導(dǎo)致一個-（２ｎ）的算法。即對于任何輸入都非常缺乏效率的算法。這就是所謂的困難問題，目前沒有已知的，效率可以用多項式來表示的算法。
表２窮舉過程和實例的解子
集
總重量
總價值
１．４背包問題的形式化描述
給定Ｗ＞０，Ｗｉ＞０，ｖｉ＞０，１≤ｉ≤ｎ，要求找出ｎ元０－１向量（ｘ１，ｘ２，∧，ｘｎ），０≤ｘｉ≤１，１≤
ｎ
ｎ
ｉ≤ｎ使得%ｗｉｘｉ≤Ｗ，而且%ｖｉｘｉ≤Ｗ達(dá)
ｉ＝１
ｉ＝１
到最大。
２０－１背包問題的一個小規(guī)模的實
例
表１
物品
重量
價值
⊙｛１｝｛２｝｛３｝｛４｝｛１，２｝｛１，３｝｛１，４｝www.ishadingyu.com｛２，３｝｛２，４｝｛３，４｝｛１，２，３｝｛１，２，４｝｛１，３，４｝｛２，３，４｝｛１，２，３，４｝
大價值為３７美元。
０２１３２３５４４３５６５７６８
０１２１０２０１５２２３２２３０２５３５
不可行
１．２０－１背包問題的形式化描述
給定Ｗ＞０，Ｗｉ＞０，ｖｉ＞０，１≤ｉ≤ｎ，要求找出ｎ元０－１向量（ｘ１，ｘ２，∧，ｘｎ），ｘｉ∈｛０，１｝，
ｎ
ｎ
１２３４
承重量Ｗ＝５
２１３２
１２美元１０美元２０美元１５美元
１≤ｉ≤ｎ使得%ｗｉｘｉ≤Ｗ，而且&ｖｉｘｉ達(dá)
ｉ＝１
ｉ＝１
到最大。因此，０－１背包問題是一個特殊的整數(shù)規(guī)劃問題。
ｎ
考慮下面數(shù)據(jù)給出的實例：
在０－１背包問題中，采用窮舉查找需要考慮給定的ｎ個物品集合的所有子集，為了找出可行的子集（也就是說，總重量不超過背包承重能力的子集）。要計算出每個子集的總重量，然后在它們中間找到價值最大的子集。
因為一個ｎ元素集合的子集數(shù)量是
ｍａｘ&ｖｉｘｉ
ｉ＝１
(
****)ｉ****+
３７
不可行不可行不可行
&ｗｘ≤Ｗ
＝１
ｉｉ
ｎ
ｘｉ∈｛０，１｝，１≤ｉ≤ｎ
１．３背包問題最優(yōu)解為｛物品１，物品２，物品４｝，最
與０－１背包問題類似，所不同的是在
作者簡介：唐敏（１９８０－），女，廣西桂林人，武漢理工大學(xué)助教、碩士，研究方向為智能計算；劉冠蓉，男，武漢理工大學(xué)教授，主要研究領(lǐng)域為智能計算、數(shù)
據(jù)挖掘；鄧國強（１９７９－），男，武漢理工大學(xué)助教、碩士，研究方向為演化計算。
月號１１１
算法與語言
３動態(tài)規(guī)劃法
表４動態(tài)規(guī)劃算法解背包問題實例次大，且能夠裝入背包，此時背包已滿。這時得到的總價值為３５，它是一個次優(yōu)解。因此，按物品效益值的非遞增次序裝包不一定能得到最優(yōu)解。
為什么每一步使目標(biāo)函數(shù)值獲得當(dāng)前最大增值的貪心策略卻沒有獲得最優(yōu)解呢？原因在于：雖然每一步獲得了效益值的極大增長，但背包容量消耗太快。
（２）以容量為度量標(biāo)準(zhǔn)。物品２（承重
３．１動態(tài)規(guī)劃法的基本思想
動態(tài)規(guī)劃法是一種強有力的算法設(shè)計技術(shù)，它被廣泛用于求解組合最優(yōu)化問題。這種技術(shù)采用自底向上的方式遞推求值，將待求解的問題分解成若干個子問題，先求解子問題，并把子問題的解存儲起來以便以后用來計算所需要求的解。
３．２遞推公式
為了設(shè)計一種動態(tài)規(guī)劃算法，需要推導(dǎo)出一個遞推關(guān)系，用較小實例的解的形式來表示背包問題的實例的解。
解決０－１背包問題的遞推式如下：
優(yōu)子集的一部分。因為Ｖ［２，３］≠Ｖ［１，３］，物品２是最優(yōu)選擇的一部分，這個最優(yōu)子集用元素Ｖ［１，３－１］來指定余下的組成部分。同樣道理，因為Ｖ［１，２］≠Ｖ［０，２］，物品１是最優(yōu)解｛物品１，物品２，物品４｝的最后一個部分。
該算法的時間效率和空間效率都屬于!（ｎＷ）。用來求最優(yōu)解的具體組成的
（１）
時間效率屬于Ｏ（ｎ＋Ｗ）。
量＝１，價值＝１０美元）承重量最小的首先裝包，剩下４個承重量，再裝入物品４（承重量＝２，價值＝１５美元），此時剩下２個承重量，裝入物品１（承重量＝２，價值＝１２美元），背包已滿，此時得到的總價值為３７美元。此時得到了該問題的最優(yōu)解。
（３）貪心法小結(jié)。從用貪心法解決０－１背包問題可以看出，采用不同的貪心策略對求解問題的結(jié)果也有所不同。所以，當(dāng)我們在使用貪心法時，必須證明該算法可以導(dǎo)致問題的最優(yōu)解。
和在動態(tài)規(guī)劃算法的情況中一樣，貪心法通常用來求解最優(yōu)化問題，即量的最大化或最小化。然而，貪心法不像動態(tài)規(guī)劃算法，它通常包含一個用以尋找局部最優(yōu)解的迭代過程。在某些實例中，這些局部最優(yōu)解轉(zhuǎn)變成了全局最優(yōu)解，而在另外一些情況下，則無法找到最優(yōu)解。
貪心法在少量計算的基礎(chǔ)上作出了正確猜想，而不急于考慮以后的情況，這樣，它一步步地來構(gòu)筑解，每一步均是建立在局部最優(yōu)解的基礎(chǔ)之上，而每一步又都擴大了部分解的規(guī)模，做出的選擇產(chǎn)生最大效益而又保持可行性。因為每一步的工作很少且基于少量信息，所得算法特別有效。
Ｖ［ｉ，ｊ］＝
ｍａｘ｛Ｖ［ｉ－１，ｊ］，ｖｉ＋Ｖ［ｉ－１，ｊ－ｗｉ］｝如果ｊ－ｗｉ≥０
Ｖ［ｉ－１，ｊ］，如果ｊ－ｗｉ＜０
定義初始條件：當(dāng)時ｊ≥０時，Ｖ［０，ｊ］＝０；當(dāng)ｉ≥０時，Ｖ［ｉ，０］＝０
（２）
我們的目標(biāo)是求Ｖ［ｎ，ｗ］，即一個給定
４
４．１
貪心法
貪心法的基本思想
貪心法總是作出在當(dāng)前看來最好的選擇，也就是說貪心法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。雖然貪心法不能對所有的問題都得到整體最優(yōu)解，但對于許多問題它能產(chǎn)生整體最優(yōu)解。在一些情況下，即使貪心法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。
貪心法是一種最直接的設(shè)計技術(shù)，它能應(yīng)用于求解多種問題。這類問題的一般特征是有ｎ個輸入以及一組約束條件，滿足約束條件的任一輸入的子集稱為可行解，其可行解由這ｎ個輸入的某個子集組成。顯然，滿足約束條件的子集可能不止一個，因此，可行解是不唯一的。為了衡量可行解的優(yōu)劣，事先也給出一定的標(biāo)準(zhǔn)。
物品中能夠放進(jìn)承重量為Ｗ的背包的子集的最大總價值，以及最優(yōu)子集本身。
３．３動態(tài)規(guī)劃表的設(shè)計
當(dāng)ｉ，ｊ＞０時，為了計算第ｉ行第ｊ列的單元格Ｖ［ｉ，ｊ］，我們拿前一行同一列的單元格與ｖｉ加上前一行左邊ｗｉ列的單元格的和作比較，計算出兩者的較大值。這個表格可以一行一行地填，也可以一列一列地填。
表３動態(tài)規(guī)劃表
５
５．１
動態(tài)規(guī)劃法和貪心法的分析
動態(tài)規(guī)劃法的設(shè)計原理
考慮表１給出的實例，表４給出了用公式（１）（２）填寫的動態(tài)規(guī)劃表。
這些標(biāo)準(zhǔn)一般以函數(shù)的形式給出，這些函數(shù)稱為目標(biāo)函數(shù)�？墒鼓繕�(biāo)函數(shù)達(dá)到極值（極大或者極小）的可行解，稱為最優(yōu)解。對于其中的某些問題，可用貪心法求解。
動態(tài)規(guī)劃是基于遞歸的技術(shù)，遞歸算法通常擁有十分簡單的歸納證明。算法設(shè)計中一個十分重要的原理，稱為最優(yōu)化原理：給定一個最優(yōu)的決策序列，每個子系列自身必須是最優(yōu)的決策序列。
在動態(tài)規(guī)劃算法中，每步所做出的選擇往往依賴于相關(guān)子問題的解。因而，只有在解出相關(guān)子問題后，才能作出選擇。
動態(tài)規(guī)劃法通常以自底向上的方式
３．４最優(yōu)解和最優(yōu)子集
因此，最大總價值為Ｖ［４，５］＝３７美元�？梢酝ㄟ^回溯這個表格單元的計算過程來求得最優(yōu)子集的組成元素。因為Ｖ［４，５］
４．２用貪心法解０－１背包問題（仍引用表
１的實例）
（１）以目標(biāo)函數(shù)為度量標(biāo)準(zhǔn)進(jìn)行裝包。物品３（承重量＝３，價值＝２０美元）效益最大的首先裝包，剩下２個承重量，再裝入物品４（承重量＝２，價值＝１５美元）效益
≠Ｖ［３，５］，物品４以及填滿背包余下５－２＝３個單位承重量的一個最優(yōu)子集都包括
在最優(yōu)解中。而后者是由元素Ｖ［３，３］來表示的。因為Ｖ［３，３］＝Ｖ［２，３］，物品３不是最
算法與語言
解各個子問題。質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用入背包。依此策略一直進(jìn)行下去，直到背５．２貪心法的基本要素
動態(tài)規(guī)劃算法或貪心法求解的關(guān)鍵特征。
包裝滿為止。
５．２．１貪心選擇性質(zhì)
５．３動態(tài)規(guī)劃法與貪心法的差異
對于０－１背包問題，貪心選擇之所以所謂貪心選擇性質(zhì)是指所求問題的
動態(tài)規(guī)劃法和貪心法都要求問題具不能得到最優(yōu)解是因為在這種情況下，它整體最優(yōu)解可以通過一系列局部最優(yōu)的有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是兩類算法的一個無法保證最終能將背包裝滿，部分閑置的選擇，即貪心選擇來達(dá)到。這是貪心法可共同點。但是，對于具有最優(yōu)子結(jié)構(gòu)的問背包空間使每單位背包空間的價值降低行的第一個基本要素，也是貪心法與動態(tài)題應(yīng)該選用動態(tài)規(guī)劃法還是貪心法求解？了。事實上，在考慮０－１背包問題時，應(yīng)比規(guī)劃算法的主要區(qū)別。
是否能用動態(tài)規(guī)劃算法求解的問題也能較選擇該物品和不選擇該物品所導(dǎo)致的貪心法所做出的貪心選擇可以依賴用貪心法求解？
最終方案，然后再做出最好選擇。由此就于以往所做過的選擇，但決不依賴于將來０－１背包問題與背包問題這兩類問
導(dǎo)出許多互相重疊的子問題。這正是該問所做的選擇，也不依賴于子問題的解。
題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)。對于０－１背包題可用動態(tài)規(guī)劃算法求解的另一重要特貪心法通常以自頂向下的方式進(jìn)行，問題，設(shè)Ａ是能夠裝入容量為Ｗ的背包征。實際上也是如此，動態(tài)規(guī)劃算法的確以迭代的方式做出相繼的貪心選擇，每做價值的物品集合，則Ａｊ＝Ａ－｛ｊ｝是ｎ－１個物可以有效地解０－１背包問題。
出一次貪心選擇就將所求問題簡化為規(guī)品１，２，∧，ｊ－１，ｊ＋１，∧，ｎ可裝入容量為Ｗ－ｗｊ動態(tài)規(guī)劃法和貪心法的基本區(qū)別在模更小的子問題。
的背包的具有最大價值的物品集合。對于于，貪心法僅產(chǎn)生一個判定序列，而動態(tài)對于一個具體問題，要確定它是否具背包問題，類似地，若它的一個最優(yōu)解包規(guī)劃法可能產(chǎn)生許多判定序列，但是按照有貪心選擇性質(zhì)，必須證明每一步所作出含物品ｊ，則從該最優(yōu)解中拿出所含的物最優(yōu)原理，包含非局部最優(yōu)的部分序列的的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。品ｊ的那部分重量ｗ，剩下的將是ｎ－１個結(jié)果肯定不可能是最優(yōu)的，所以不予考首先考察問題的一個整體最優(yōu)解，并證明原重物品１，２，∧，ｊ－１，ｊ＋１，∧，ｎ以及重為ｗｊ－
慮。設(shè)計貪心法的困難部分就是要證明該可修改這個最優(yōu)解，使其以貪心選擇開ｗ的物品ｊ中可裝入容量為Ｗ－ｗ的背包
算法確實是求解了它所需要解決的問題。
始。做出貪心選擇后，原問題簡化為規(guī)模且具有最大價值的物品。
參考文獻(xiàn)：
更小的類似子問題。然后，用數(shù)學(xué)歸納法雖然這兩個問題極為相似，但背包問證明，通過每一步做貪心選擇，最終可得題可以用貪心法求解，而０－１背包問題卻［１］王曉東．算法設(shè)計與分析［Ｍ］．北京：清華大
到問題的整體最優(yōu)解。其中，證明貪心選不能用貪心法求解。用貪心法解背包問題學(xué)出版社，２００３．
擇后的問題簡化為規(guī)模更小的類似子問的基本步驟是：首先計算每種物品單位重［２］宋文，吳晟，杜亞軍．算法設(shè)計與分析［Ｍ］．
重慶：重慶大學(xué)出版社，２００２．
題的關(guān)鍵在于利用該問題的最優(yōu)子結(jié)構(gòu)量的價值ｖｉ／ｗｉ，然后，依貪心選擇策略，將［３］ＡｎａｎｙＬｅｖｉｔｉｎ．算法設(shè)計與分析基礎(chǔ)［Ｍ］．北
性質(zhì)。
盡可能多的單位重量價值最高的物品裝京：清華大學(xué)出版社，２００４．
５．２．２最優(yōu)子結(jié)構(gòu)性質(zhì)
入背包。若將這種物品全部裝入背包后，［４］盧開澄．計算機算法導(dǎo)引—設(shè)計與分析［Ｍ］．
當(dāng)一個問題的最優(yōu)解包含其子問題
背包內(nèi)的物品總重量未超過Ｗ，則選擇單北京：清華大學(xué)出版社，２００３．
的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性
位重量價值次高的物品并盡可能多地裝
（責(zé)任編輯：曙光）
Ｓｏｌｖｉｎｇ０－１ＫｎａｐｓａｃｋＰｒｏｂｌｅｍｓｂｙＤｙｎａｍｉｃＰｒｏｇｒａｍｍｉｎｇＭｅｔｈｏｄａｎｄＧｒｅｅｄｙＭｅｔｈｏｄ
ＴＡＮＧＭｉｎ，ＬＩＵＧｕａｎ－ｒｏｎｇ１，ＤＥＮＧＧｕｏ－ｑｉａｎｇ２
（１．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＷｕｈａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ４３００７０，Ｃｈｉｎａ；
２．ＳｃｈｏｏｌｏｆＮａｔｕｒｅＳｃｉｅｎｃｅ，ＷｕｈａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｄｏｇｙ，Ｗｕｈａｎ４３００７０，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：０－１ｋｎａｐｓａｃｋｐｒｏｂｌｅｍｓａｎｄｋｎａｐｓａｃｋｐｒｏｂｌｅｍｓａｒｅａｃｌａｓｓｉｃａｌＮＰｈａｒｄｐｒｏｂｌｅｍｓ．Ｔｈｉｓｐａｐｅｒａｄｏｐｔｓｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇｍｅｔｈｏｄａｎｄｇｒｅｅｄｙｍｅｔｈｏｄｔｏｓｏｌｖｅｓｕｃｈｐｒｏｂｌｅｍｓ，ｔｈｅｎａｎａｌｙｚｅｓａｎｄｃｏｍｐａｒｅｓｔｈｅｄｉｆｆｅｒｅｎｃｅｓｏｆｔｗｏａｌｇｏ－ｒｉｔｈｍｓ．
Ｋｅｙｗｏｒｄｓ：０－１ｋｎａｐｓａｃｋｐｒｏｂｌｅｍｓ；ｋｎａｐｓａｃｋｐｒｏｂｌｅｍｓ；ｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇｍｅｔｈｏｄ；ｇｒｅｅｄｙｍｅｔｈｏｄ
月號１１３
【用動態(tài)規(guī)劃法和貪心法解決背包問題】相關(guān)文章：
用智慧解決問題作文08-10
教案：用除法解決問題04-24
金岳霖對歸納問題的表述和邏輯解決05-02
《用除法解決實際問題》教案03-04
用比例解決問題教學(xué)反思04-22
用連乘解決問題教學(xué)反思04-22
用新理念解決政工新問題04-26
8和9解決問題課后反思04-12