淺談計算機中背包問題的動態規劃解法

張亞威 王中帥 王培英

摘要：背包問題和動態規劃問題是計算機專業學生算法學習中的重點。本文介紹了背包問題和動態規劃的基本概念，然后通過實例詳細的論述了背包型動態規劃的實現過程。

關鍵詞：0-1背包；動態規劃；背包型動態規劃1什么是背包問題

背包問題(Knapsack problem)是一種組合優化的NP完全問題。大致求解的問題類型：給定N件物品，每件物品都有自己的體積和價值，在背包總體積一定的情況下，我們如何選擇，才能使得背包內物品的總價值最高。它是在1978年由Merkel和Hellman提出的。與此相類似的問題常出現在商業、組合數學、計算復雜性理論、密碼學和應用數學等領域中。

2什么是動態規劃

動態規劃(dynamic programming)是運籌學的一個分支，它是解決多階段決策過程的最優化的數學方法。20世紀50年代初美國數學家貝爾曼(R.E.Bellman)等人在研究多階段決策過程(multistep decision process)的優化問題時，把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解，創立了解決這類過程優化問題的新方法——動態規劃。1957年出版了他的名著Dynamic Programming，這是該領域的第一本著作

3什么是背包問題的動態規劃解法

所謂背包問題的動態規劃解法其實也就是運用動態規劃的思想快速、高效的求得背包問題的最優解的一種解題方式。我們知道對于背包問題：對于任何一件物品，我們都可以選擇往背包里放或者不放；而解決動態規劃的最核心一點：就是必須求得問題的狀態轉移方程！背包問題的選擇放或者不放這兩種決策方式恰恰會導致兩種不同的狀態，完全符合動態規劃所能解決的類型。

4舉例說明背包型動態規劃的具體過程

例如：從前有一個地主老財，他的家鄉發生了戰亂，為了躲避這場戰亂，他決定帶領全家人搬遷到一個沒有戰亂的地方，所以他準備了一個大箱子，想把家里的值錢的東西都帶走，可是家里的東西太多了，根本不能完全帶走，所以他想讓他的管家幫他一下，告訴他應該裝哪些東西，才能使帶走的東西總價值最大，并告訴他總價值是多少。下面會給出箱子的總體積V和物品的件數N，以及每件物品的體積v和價值c；任何一件物品都不可分割，因為物品一旦分割便一文不值。為了既能說明問題，又能夠使描述的最簡潔，我們把數值都定義的小一些！假設箱子的總體積為10，物品的件數為5；接下來的5件物品的體積和價值分別為：第一件：體積為8 價值為2；第二件：體積為4 價值為5；第三件：體積為3 價值為5；第四件：體積為4 價值為3；第五件：體積為2價值為2。

解題思路：首先我們初始化11個箱子，表示箱子可能會出現的11種狀態：如dp[0]=0表示背包內物體所占用的體積為0時，背包內物品的總價值0；dp[1]=0表示背包內物體所占用的體積為1時，背包內物品的總價值0；??????；dp[10]=0 表示背包內物體所占用的體積為10時，背包內物品的總價值0。接下來我們來看第一組數組：體積8 價值2，我們考慮一下如果把該物品裝進箱子，箱子中物品占用的體積會達到多少呢？很明顯，箱子內的物品占用的體積有可能是8體積，9體積，10體積。因為如果箱子原先是空的，那么把該物品放進去后，所有物品占用的總體積為8；如果箱子原先已經放了1體積物品了，那么把該物品放進去后，所有物品占用的總體積為9；如果箱子原先已經放了2體積物品了，那么把該物品放進去后，所有物品占用的總體積為10；如果箱子原先已經放了3體積物品了，8+3=11，大于箱子的總體積，放不下！這是考慮到把物品放進箱子里，那么什么時候我們不把物品放進箱子里呢？還以上面的數據為例：如果把這件物品放進去，達到8體積的狀態，價值為dp[0]+2，那么我們用dp[8]和dp[0]+2比較，如果dp[8]

列號0,1,2,3......10表示箱子中物品占用的總體積；行號0,1,2,3,4,5表示第i=0,1,2,3,4,5件物品可放入箱子中的情況下，箱子中物品的最大價值。

很明顯，箱子中放入物品后，總的最大價值為12。

綜上所述，背包型動態規劃是算法中的經典問題之一，也是ACM國際大學生程序設計競賽中的高頻考點。由于競賽中試題對該算法的考察比較靈活，因此必須深入學習該算法的思想，熟練掌握該算法的原理，才能在賽場上取得勝利，也才能在實際生活中得到廣泛應用。

[參考文獻]

[1]田烽楠,王于.求解0-1背包問題算法綜述.軟件導刊，2009,8(1):59-61.

[2]馬,朱剛,寧愛兵.蟻群優化算法.北京:科學出版社，2010.

[3]崔遜學.多目標進化算法及其應用.北京:國防工業出版社，2008.

[4]于惠.遺傳算法的改進研究及在背包問題中的應用.山東師范大學碩士論文，2009.