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