淺談?dòng)?jì)算機(jī)中背包問(wèn)題的動(dòng)態(tài)規(guī)劃解法

張亞威 王中帥 王培英

摘要：背包問(wèn)題和動(dòng)態(tài)規(guī)劃問(wèn)題是計(jì)算機(jī)專業(yè)學(xué)生算法學(xué)習(xí)中的重點(diǎn)。本文介紹了背包問(wèn)題和動(dòng)態(tài)規(guī)劃的基本概念，然后通過(guò)實(shí)例詳細(xì)的論述了背包型動(dòng)態(tài)規(guī)劃的實(shí)現(xiàn)過(guò)程。

關(guān)鍵詞：0-1背包；動(dòng)態(tài)規(guī)劃；背包型動(dòng)態(tài)規(guī)劃1什么是背包問(wèn)題

背包問(wèn)題(Knapsack problem)是一種組合優(yōu)化的NP完全問(wèn)題。大致求解的問(wèn)題類型：給定N件物品，每件物品都有自己的體積和價(jià)值，在背包總體積一定的情況下，我們?nèi)绾芜x擇，才能使得背包內(nèi)物品的總價(jià)值最高。它是在1978年由Merkel和Hellman提出的。與此相類似的問(wèn)題常出現(xiàn)在商業(yè)、組合數(shù)學(xué)、計(jì)算復(fù)雜性理論、密碼學(xué)和應(yīng)用數(shù)學(xué)等領(lǐng)域中。

2什么是動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，它是解決多階段決策過(guò)程的最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國(guó)數(shù)學(xué)家貝爾曼(R.E.Bellman)等人在研究多階段決策過(guò)程(multistep decision process)的優(yōu)化問(wèn)題時(shí)，把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類過(guò)程優(yōu)化問(wèn)題的新方法——?jiǎng)討B(tài)規(guī)劃。1957年出版了他的名著Dynamic Programming，這是該領(lǐng)域的第一本著作

3什么是背包問(wèn)題的動(dòng)態(tài)規(guī)劃解法

所謂背包問(wèn)題的動(dòng)態(tài)規(guī)劃解法其實(shí)也就是運(yùn)用動(dòng)態(tài)規(guī)劃的思想快速、高效的求得背包問(wèn)題的最優(yōu)解的一種解題方式。我們知道對(duì)于背包問(wèn)題：對(duì)于任何一件物品，我們都可以選擇往背包里放或者不放；而解決動(dòng)態(tài)規(guī)劃的最核心一點(diǎn)：就是必須求得問(wèn)題的狀態(tài)轉(zhuǎn)移方程！背包問(wèn)題的選擇放或者不放這兩種決策方式恰恰會(huì)導(dǎo)致兩種不同的狀態(tài)，完全符合動(dòng)態(tài)規(guī)劃所能解決的類型。

4舉例說(shuō)明背包型動(dòng)態(tài)規(guī)劃的具體過(guò)程

例如：從前有一個(gè)地主老財(cái)，他的家鄉(xiāng)發(fā)生了戰(zhàn)亂，為了躲避這場(chǎng)戰(zhàn)亂，他決定帶領(lǐng)全家人搬遷到一個(gè)沒(méi)有戰(zhàn)亂的地方，所以他準(zhǔn)備了一個(gè)大箱子，想把家里的值錢的東西都帶走，可是家里的東西太多了，根本不能完全帶走，所以他想讓他的管家?guī)退幌?，告訴他應(yīng)該裝哪些東西，才能使帶走的東西總價(jià)值最大，并告訴他總價(jià)值是多少。下面會(huì)給出箱子的總體積V和物品的件數(shù)N，以及每件物品的體積v和價(jià)值c；任何一件物品都不可分割，因?yàn)槲锲芬坏┓指畋阋晃牟恢?。為了既能說(shuō)明問(wèn)題，又能夠使描述的最簡(jiǎn)潔，我們把數(shù)值都定義的小一些！假設(shè)箱子的總體積為10，物品的件數(shù)為5；接下來(lái)的5件物品的體積和價(jià)值分別為：第一件：體積為8 價(jià)值為2；第二件：體積為4 價(jià)值為5；第三件：體積為3 價(jià)值為5；第四件：體積為4 價(jià)值為3；第五件：體積為2價(jià)值為2。

解題思路：首先我們初始化11個(gè)箱子，表示箱子可能會(huì)出現(xiàn)的11種狀態(tài)：如dp[0]=0表示背包內(nèi)物體所占用的體積為0時(shí)，背包內(nèi)物品的總價(jià)值0；dp[1]=0表示背包內(nèi)物體所占用的體積為1時(shí)，背包內(nèi)物品的總價(jià)值0；??????；dp[10]=0 表示背包內(nèi)物體所占用的體積為10時(shí)，背包內(nèi)物品的總價(jià)值0。接下來(lái)我們來(lái)看第一組數(shù)組：體積8 價(jià)值2，我們考慮一下如果把該物品裝進(jìn)箱子，箱子中物品占用的體積會(huì)達(dá)到多少呢？很明顯，箱子內(nèi)的物品占用的體積有可能是8體積，9體積，10體積。因?yàn)槿绻渥釉仁强盏模敲窗言撐锲贩胚M(jìn)去后，所有物品占用的總體積為8；如果箱子原先已經(jīng)放了1體積物品了，那么把該物品放進(jìn)去后，所有物品占用的總體積為9；如果箱子原先已經(jīng)放了2體積物品了，那么把該物品放進(jìn)去后，所有物品占用的總體積為10；如果箱子原先已經(jīng)放了3體積物品了，8+3=11，大于箱子的總體積，放不下！這是考慮到把物品放進(jìn)箱子里，那么什么時(shí)候我們不把物品放進(jìn)箱子里呢？還以上面的數(shù)據(jù)為例：如果把這件物品放進(jìn)去，達(dá)到8體積的狀態(tài)，價(jià)值為dp[0]+2，那么我們用dp[8]和dp[0]+2比較，如果dp[8]

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

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

綜上所述，背包型動(dòng)態(tài)規(guī)劃是算法中的經(jīng)典問(wèn)題之一，也是ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽中的高頻考點(diǎn)。由于競(jìng)賽中試題對(duì)該算法的考察比較靈活，因此必須深入學(xué)習(xí)該算法的思想，熟練掌握該算法的原理，才能在賽場(chǎng)上取得勝利，也才能在實(shí)際生活中得到廣泛應(yīng)用。

[參考文獻(xiàn)]

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

[2]馬,朱剛,寧愛(ài)兵.蟻群優(yōu)化算法.北京:科學(xué)出版社，2010.

[3]崔遜學(xué).多目標(biāo)進(jìn)化算法及其應(yīng)用.北京:國(guó)防工業(yè)出版社，2008.

[4]于惠.遺傳算法的改進(jìn)研究及在背包問(wèn)題中的應(yīng)用.山東師范大學(xué)碩士論文，2009.