用動(dòng)態(tài)規(guī)劃法和貪心法解決背包問(wèn)題.doc

用動(dòng)態(tài)規(guī)劃法和貪心法解決背包問(wèn)題 算法與語(yǔ)言 用動(dòng)態(tài)規(guī)劃法和貪心法解決背包問(wèn)題 唐 敏，劉冠蓉，鄧國(guó)強(qiáng) （武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北武漢； 武漢理工大學(xué)理學(xué)院，湖北武漢） 摘要：背包問(wèn)題和背包問(wèn)題是一類經(jīng)典的困難問(wèn)題。采用動(dòng)態(tài)規(guī)劃法和貪心法對(duì)該問(wèn)題進(jìn)行求 解，分析和比較這兩種算法在求解同一問(wèn)題時(shí)的差異。 關(guān)鍵詞：背包問(wèn)題；背包問(wèn)題；動(dòng)態(tài)規(guī)劃法；貪心法： ： ：（） 背包問(wèn)題與背包問(wèn)題 背包問(wèn)題 給定個(gè)重量為（，）價(jià)值為（，）的物品和一個(gè)承重量為的背包，求這些物品中最有價(jià)值的一個(gè)子集，并且要能夠裝到背包中。 在選擇裝入背包的物品時(shí)，對(duì)每種物品只有兩種選擇，即裝入背包或不裝入背包。不能將物品裝入背包多次，也不能只裝入部分的物品。在這里假設(shè)所有的重量和背包的承重量都是正整數(shù)。 選擇物品裝入背包時(shí)，可以選擇物品的一部分，而不一定要全部裝入背包。 ，所以不論生成獨(dú)立子集的效率有多高， 窮舉查找都會(huì)導(dǎo)致一個(gè)-（）的算法。即對(duì)于任何輸入都非常缺乏效率的算法。這就是所謂的困難問(wèn)題，目前沒(méi)有已知的，效率可以用多項(xiàng)式來(lái)表示的算法。 表窮舉過(guò)程和實(shí)例的解子 集 總重量 總價(jià)值 背包問(wèn)題的形式化描述 給定，要求找出元向量（，）， 使得%，而且%達(dá) 到最大。 背包問(wèn)題的一個(gè)小規(guī)模的實(shí) 例 表 物品 重量 價(jià)值 ， 大價(jià)值為美元。 不可行 背包問(wèn)題的形式化描述 給定，要求找出元向量（，）， 承重量 美元美元美元美元 使得%，而且&達(dá) 到最大。因此，背包問(wèn)題是一個(gè)特殊的整數(shù)規(guī)劃問(wèn)題。 考慮下面數(shù)據(jù)給出的實(shí)例： 在背包問(wèn)題中，采用窮舉查找需要考慮給定的個(gè)物品集合的所有子集，為了找出可行的子集（也就是說(shuō)，總重量不超過(guò)背包承重能力的子集）。要計(jì)算出每個(gè)子集的總重量，然后在它們中間找到價(jià)值最大的子集。 因?yàn)橐粋€(gè)元素集合的子集數(shù)量是 & ( *)*+ 不可行不可行不可行 & ， 背包問(wèn)題最優(yōu)解為物品，物品，物品，最 與背包問(wèn)題類似，所不同的是在 作者簡(jiǎn)介：唐敏（），女，廣西桂林人，武漢理工大學(xué)助教、碩士，研究方向?yàn)橹悄苡?jì)算；劉冠蓉，男，武漢理工大學(xué)教授，主要研究領(lǐng)域?yàn)橹悄苡?jì)算、數(shù) 據(jù)挖掘；鄧國(guó)強(qiáng)（），男，武漢理工大學(xué)助教、碩士，研究方向?yàn)檠莼?jì)算。 月號(hào) 算法與語(yǔ)言 動(dòng)態(tài)規(guī)劃法 表動(dòng)態(tài)規(guī)劃算法解背包問(wèn)題實(shí)例次大，且能夠裝入背包，此時(shí)背包已滿。這時(shí)得到的總價(jià)值為，它是一個(gè)次優(yōu)解。因此，按物品效益值的非遞增次序裝包不一定能得到最優(yōu)解。 為什么每一步使目標(biāo)函數(shù)值獲得當(dāng)前最大增值的貪心策略卻沒(méi)有獲得最優(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)化問(wèn)題。這種技術(shù)采用自底向上的方式遞推求值，將待求解的問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，并把子問(wèn)題的解存儲(chǔ)起來(lái)以便以后用來(lái)計(jì)算所需要求的解。 遞推公式 為了設(shè)計(jì)一種動(dòng)態(tài)規(guī)劃算法，需要推導(dǎo)出一個(gè)遞推關(guān)系，用較小實(shí)例的解的形式來(lái)表示背包問(wèn)題的實(shí)例的解。 解決背包問(wèn)題的遞推式如下： 優(yōu)子集的一部分。因?yàn)椋锲肥亲顑?yōu)選擇的一部分，這個(gè)最優(yōu)子集用元素，來(lái)指定余下的組成部分。同樣道理，因?yàn)?，物品是最?yōu)解物品，物品，物品的最后一個(gè)部分。 該算法的時(shí)間效率和空間效率都屬于!（）。用來(lái)求最優(yōu)解的具體組成的 （） 時(shí)間效率屬于（）。 量，價(jià)值美元）承重量最小的首先裝包，剩下個(gè)承重量，再裝入物品（承重量，價(jià)值美元），此時(shí)剩下個(gè)承重量，裝入物品（承重量，價(jià)值美元），背包已滿，此時(shí)得到的總價(jià)值為美元。此時(shí)得到了該問(wèn)題的最優(yōu)解。 （）貪心法小結(jié)。從用貪心法解決背包問(wèn)題可以看出，采用不同的貪心策略對(duì)求解問(wèn)題的結(jié)果也有所不同。所以，當(dāng)我們?cè)谑褂秘澬姆〞r(shí)，必須證明該算法可以導(dǎo)致問(wèn)題的最優(yōu)解。 和在動(dòng)態(tài)規(guī)劃算法的情況中一樣，貪心法通常用來(lái)求解最優(yōu)化問(wèn)題，即量的最大化或最小化。然而，貪心法不像動(dòng)態(tài)規(guī)劃算法，它通常包含一個(gè)用以尋找局部最優(yōu)解的迭代過(guò)程。在某些實(shí)例中，這些局部最優(yōu)解轉(zhuǎn)變成了全局最優(yōu)解，而在另外一些情況下，則無(wú)法找到最優(yōu)解。 貪心法在少量計(jì)算的基礎(chǔ)上作出了正確猜想，而不急于考慮以后的情況，這樣，它一步步地來(lái)構(gòu)筑解，每一步均是建立在局部最優(yōu)解的基礎(chǔ)之上，而每一步又都擴(kuò)大了部分解的規(guī)模，做出的選擇產(chǎn)生最大效益而又保持可行性。因?yàn)槊恳徊降墓ぷ骱苌偾一谏倭啃畔?，所得算法特別有效。 ， ，如果 ，如果 定義初始條件：當(dāng)時(shí)時(shí)，；當(dāng)時(shí)， （） 我們的目標(biāo)是求，即一個(gè)給定 貪心法 貪心法的基本思想 貪心法總是作出在當(dāng)前看來(lái)最好的選擇，也就是說(shuō)貪心法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。雖然貪心法不能對(duì)所有的問(wèn)題都得到整體最優(yōu)解，但對(duì)于許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。在一些情況下，即使貪心法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。 貪心法是一種最直接的設(shè)計(jì)技術(shù)，它能應(yīng)用于求解多種問(wèn)題。這類問(wèn)題的一般特征是有個(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ì)于其中的某些問(wèn)題，可用貪心法求解。 動(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)子問(wèn)題的解。因而，只有在解出相關(guān)子問(wèn)題后，才能作出選擇。 動(dòng)態(tài)規(guī)劃法通常以自底向上的方式 最優(yōu)解和最優(yōu)子集 因此，最大總價(jià)值為，美元。可以通過(guò)回溯這個(gè)表格單元的計(jì)算過(guò)程來(lái)求得最優(yōu)子集的組成元素。因?yàn)椋?用貪心法解背包問(wèn)題（仍引用表 的實(shí)例） （）以目標(biāo)函數(shù)為度量標(biāo)準(zhǔn)進(jìn)行裝包。物品（承重量，價(jià)值美元）效益最大的首先裝包，剩下個(gè)承重量，再裝入物品（承重量，價(jià)值美元）效益 ，物品以及填滿背包余下個(gè)單位承重量的一個(gè)最優(yōu)子集都包括 在最優(yōu)解中。而后者是由元素，來(lái)表示的。因?yàn)?，物品不是?算法與語(yǔ)言 解各個(gè)子問(wèn)題。質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用入背包。依此策略一直進(jìn)行下去，直到背貪心法的基本要素 動(dòng)態(tài)規(guī)劃算法或貪心法求解的關(guān)鍵特征。 包裝滿為止。 貪心選擇性質(zhì) 動(dòng)態(tài)規(guī)劃法與貪心法的差異 對(duì)于背包問(wèn)題，貪心選擇之所以所謂貪心選擇性質(zhì)是指所求問(wèn)題的 動(dòng)態(tài)規(guī)劃法和貪心法都要求問(wèn)題具不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是兩類算法的一個(gè)無(wú)法保證最終能將背包裝滿，部分閑置的選擇，即貪心選擇來(lái)達(dá)到。這是貪心法可共同點(diǎn)。但是，對(duì)于具有最優(yōu)子結(jié)構(gòu)的問(wèn)背包空間使每單位背包空間的價(jià)值降低行的第一個(gè)基本要素，也是貪心法與動(dòng)態(tài)題應(yīng)該選用動(dòng)態(tài)規(guī)劃法還是貪心法求解？了。事實(shí)上，在考慮背包問(wèn)題時(shí)，應(yīng)比規(guī)劃算法的主要區(qū)別。 是否能用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題也能較選擇該物品和不選擇該物品所導(dǎo)致的貪心法所做出的貪心選擇可以依賴用貪心法求解？ 最終方案，然后再做出最好選擇。由此就于以往所做過(guò)的選擇，但決不依賴于將來(lái)背包問(wèn)題與背包問(wèn)題這兩類問(wèn) 導(dǎo)出許多互相重疊的子問(wèn)題。這正是該問(wèn)所做的選擇，也不依賴于子問(wèn)題的解。 題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)。對(duì)于背包題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特貪心法通常以自頂向下的方式進(jìn)行，問(wèn)題，設(shè)是能夠裝入容量為的背包征。實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確以迭代的方式做出相繼的貪心選擇，每做價(jià)值的物品集合，則是個(gè)物可以有效地解背包問(wèn)題。 出一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)品，可裝入容量為動(dòng)態(tài)規(guī)劃法和貪心法的基本區(qū)別在模更小的子問(wèn)題。 的背包的具有最大價(jià)值的物品集合。對(duì)于于，貪心法僅產(chǎn)生一個(gè)判定序列，而動(dòng)態(tài)對(duì)于一個(gè)具體問(wèn)題，要確定它是否具背包問(wèn)題，類似地，若它的一個(gè)最優(yōu)解包規(guī)劃法可能產(chǎn)生許多判定序列，但是按照有貪心選擇性質(zhì)，必須證明每一步所作出含物品，則從該最優(yōu)解中拿出所含的物最優(yōu)原理，包含非局部最優(yōu)的部分序列的的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。品的那部分重量，剩下的將是個(gè)結(jié)果肯定不可能是最優(yōu)的，所以不予考首先考察問(wèn)題的一個(gè)整體最優(yōu)解，并證明原重物品，以及重為 慮。設(shè)計(jì)貪心法的困難部分就是要證明該可修改這個(gè)最優(yōu)解，使其以貪心選擇開(kāi)的物品中可裝入容量為的背包 算法確實(shí)是求解了它所需要解決的問(wèn)題。 始。做出貪心選擇后，原問(wèn)題簡(jiǎn)化為規(guī)模且具有最大價(jià)值的物品。 參考文獻(xiàn)： 更小的類似子問(wèn)題。然后，用數(shù)學(xué)歸納法雖然這兩個(gè)問(wèn)題極為相似，但背包問(wèn)證明，通過(guò)每一步做貪心選擇，最終可得題可以用貪心法求解，而背包問(wèn)題卻王曉東算法設(shè)計(jì)與分析北京：清華大 到問(wèn)題的整體最優(yōu)解。其中，證明貪心選不能用貪心法求解。用貪心法解背包問(wèn)題學(xué)出版社， 擇后的問(wèn)題簡(jiǎn)化為規(guī)模更小的類似子問(wèn)的基本步驟是：首先計(jì)算每種物品單位重宋文，吳晟，杜亞軍算法設(shè)計(jì)與分析 重慶：重慶大學(xué)出版社， 題的關(guān)鍵在于利用該問(wèn)題的最優(yōu)子結(jié)構(gòu)