淺談0—1背包問題的常用算法

摘 要：0-1背包問題是典型的NP-完全問題，無論從理論上還是實踐上都有一定的研究意義。本文綜述了幾種0-1背包問題的常用算法，分析算法的優劣，預測0-1背包問題的發展方向。

關鍵詞：0-1背包問題；動態規劃法；貪心法；分支界限法

中圖分類號：TP18 文獻標識碼：A 文章編號：1674-7712 （2013） 20-0000-01

0-1背包問題是背包問題的一個特例，二者的區別在于物品裝入背包過程中是否可以部分裝入；可以部分裝入的屬于背包問題研究范疇，不可以部分裝入的背包問題可以描述為0-1背包問題。

0-1背包問題的應用廣泛，許多的實際問題都可以轉化為0-1背包問題。例如：貸款組合優化決策問題、項目投資問題、預算控制、貨物裝載等。所以，0-1背包問題的算法研究無論是在理論上還是在實踐中都具有深遠的意義。

一、0-1背包問題的抽象模型描述

（一）0-1背包問題描述

（二）抽象模型描述

二、常用的0-1背包問題算法

（一）蠻力法

蠻力法又稱窮舉法或枚舉法，是一種簡單、直接、有效的方法，是初學者入門的方法。蠻力法要求遍歷所有可能情況一次且僅一次，篩選出符合要求的解。

應用蠻力法求解0-1背包問題，需要考慮給定的n個物品集合的所有子集，找出所有總重量不超過背包容量的子集，計算每個可能子集的總價值，然后找出價值最大的子集。

對于一個具有n個元素的集合，其子集數量是2n ，所以，不論生成子集的算法效率有多高，蠻力法求解0-1背包問題都會導致一個 （2n ）的算法。

（二）動態規劃法

動態規劃法是一種通用的算法設計技術用來求解多階段決策最優化問題。這類問題都滿足最優性原理，即原問題的最優性包含著子問題的最優性。

應用動態規劃法求解0-1背包問題，可以將0-1背包問題看作一個多階段決策最優化問題。n個物品集合的所有子集可以看作該問題的所有可行解；這些可行解都是滿足約束條件的，可行解可能不止一個，通過目標函數找到最優解。

（三）貪心法

貪心法也是求解最優化問題，但貪心法與動態規劃法考慮問題的角度是不同的。動態規劃法是從整體考慮最優化問題，整體最優包含著局部的最優；貪心法不是從整體最優考慮，它所做出的選擇只是在某種意義上的局部最優，這種局部最優選擇并不總能獲得整體最優解，但通常能獲得近似最優解。

貪心法的核心是貪心策略的選擇，選擇能夠得到最優解的貪心策略是貪心法的研究目標。應用貪心法解決0-1背包問題，貪心策略的選擇尤為重要。

可以從不同的角度考量不同的貪心策略。在0-1背包問題上，貪心策略至少有三種：

第一種貪心策略能夠保證盡可能快的增加背包的總價值，但背包的容量消耗的也很快，使得裝入背包的物品數量減少，不能保證得到最優結果；

第二種貪心策略能夠保證盡可能多的裝入物品，但裝入背包的物品多不一定物品的總價值就最大，從而不能保證得到最優結果；

第三鐘貪心策略，在背包價值增長和背包容量消耗二者之間找到平衡，是一種不錯的貪心策略。

在實際應用中貪心法不能使0-1背包問題得到最優解，也就是說貪心法不能夠求解0-1背包問題。在0-1背包問題中，物品不允許分割裝入背包，因此，無法保證最終能將背包裝滿，部分閑置的背包容量使背包的單位重量價值降低了。但貪心法是求解背包問題的有效方法。

（四）分支界限法

分支界限法按廣度優先策略搜索問題的解空間樹，在搜索過程中，對待處理的結點根據限界函數估算目標函數的可能取值，從中選取使目標函數取極值的結點優先進行廣度搜索，從而不斷調整搜索方向，盡快找到問題的解。

三、結束語

上述只是求解0-1背包問題的幾種常用算法，除此之外，研究解決0-1背包問題的算法還有很多，如粒子群優化算法、人工神經網絡算法、克隆選擇算法、混合算法等，各種算法都各有優劣，取長補短是0-1背包問題未來算法研究的方向。

參考文獻：

[1]田烽楠，王于.求解0-1背包問題算法綜述[J].軟件導刊，2009，1.

[2]王紅梅.算法設計與分析[M].北京：清華大學出版社，2013，4.

[3]趙建英.0-1背包問題的非線性降維近似算法[J].內蒙古師范大學學報，2007，1.