動(dòng)態(tài)規(guī)劃求解0-1背包問(wèn)題

1、基于MATLAB的0-1背包問(wèn)題的動(dòng)態(tài)規(guī)劃求解數(shù)學(xué)實(shí)驗(yàn)論文動(dòng)態(tài)規(guī)劃算法求解0-1背包問(wèn)題郭倫指導(dǎo)教師名：郭德龍職 稱：副教授單 位：數(shù)學(xué)與統(tǒng)計(jì)學(xué)院專 業(yè) 名 稱：B15信息與計(jì)算科學(xué)動(dòng)態(tài)規(guī)劃算法求解0-1背包問(wèn)題摘 要本文主要闡述了基于MATLAB的0-1背包問(wèn)題動(dòng)態(tài)規(guī)劃的求解。0-1背包問(wèn)題（Knapsack Problem，簡(jiǎn)稱KP問(wèn)題）是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，具有廣泛的實(shí)際應(yīng)用背景，以及在理論研究領(lǐng)域也有其相當(dāng)?shù)拇硇?。KP問(wèn)題的求解，在生活中多有應(yīng)用，如貨源分配、輪船裝載、項(xiàng)目選擇等等都有它的身影。并且它還常常作為其他相對(duì)復(fù)雜的組合問(wèn)題的一個(gè)特殊解，但當(dāng)問(wèn)題

2、規(guī)模過(guò)大時(shí)，如果想要得到最優(yōu)解是極其困難的，因此對(duì)大規(guī)模的0-1背包問(wèn)題的研究無(wú)論是在理論研究領(lǐng)域還是實(shí)際應(yīng)用背景都有其重要的意義。動(dòng)態(tài)規(guī)劃算法是五種常用的算法之一，通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。其基本思想是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題，經(jīng)分解得到子問(wèn)題往往不是互相獨(dú)立的。若用分治法來(lái)解這類問(wèn)題，則分解得到的子問(wèn)題數(shù)目太多，有些子問(wèn)題被重復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間。我們可以用一個(gè)表來(lái)記錄所有已解的

3、子問(wèn)題的答案。不管該子問(wèn)題以后是否被用到，只要它被計(jì)算過(guò)，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思路。具體的動(dòng)態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。由于我們可以用一個(gè)表來(lái)記錄所有已解子問(wèn)題的答案，需要用到的時(shí)候直接調(diào)用，所以動(dòng)態(tài)規(guī)劃法又叫“填表法”。關(guān)鍵詞：KP問(wèn)題，0-1背包問(wèn)題，動(dòng)態(tài)規(guī)劃，最優(yōu)解，背包問(wèn)題，MATLAB，基于MATLAB的0-1背包問(wèn)題動(dòng)態(tài)規(guī)劃的求解一問(wèn)題重述給定一個(gè)容量為C的背包和n個(gè)物品，其中物品i的體積為vi,價(jià)值為wi(i=1,2,3,n),要從這n個(gè)物品中挑選出若干件放入背包，每個(gè)物品只能挑選一次，使得放入物品的總體積不超過(guò)C，而價(jià)值達(dá)到最大，并找出一

4、種添放物品的方案。二模型假設(shè)0-1背包問(wèn)題的為：設(shè)xi為一個(gè)二進(jìn)制量，xi=1表示將物品i放入背包，xi=0表示物品不裝入背包，問(wèn)題的目的在于確定一個(gè)二進(jìn)制的數(shù)組（x1,x2,x3xn）使得maxi=1nxiwi即：maxi=1nxiwi xi(0,1) 且 i=1nxiviC三符號(hào)說(shuō)明C:背包的容量V:物品的體積W:物品的價(jià)值n:物品的數(shù)量f：用于狀態(tài)交換的矩陣t：用于輸入物品是否裝入背包，0表示裝入，1表示不裝入四問(wèn)題分析對(duì)于0-1背包問(wèn)題，每個(gè)物品都只有兩種選擇，裝入或者不裝入兩種，可以用一個(gè)二維數(shù)組fij表示物品是否裝入背包。我們要做的是找出可以放入背包的物品使得背包內(nèi)的價(jià)值最大，利用

5、遞歸思想，用子問(wèn)題定義狀態(tài)：即fij表示前i件物品恰放入一個(gè)容量為j的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：fij=maxfi-1j,fi-1j-vi+wi對(duì)于第i個(gè)物品，我們可以拿這個(gè)物品的體積同背包內(nèi)剩余的體積相比較，如果背包內(nèi)剩余的容量大于物品的體積，那么這個(gè)物品就可以裝入背包，這時(shí)我們只要判斷裝入這個(gè)物品后和裝入這個(gè)物品前的價(jià)值哪一個(gè)更大，就可以通過(guò)這種遞歸的方式球的背包能裝入的最大價(jià)值。五模型建立與求解我們知道，動(dòng)態(tài)規(guī)劃算法又叫填表法，填表的順序?yàn)樽缘紫蛏?，自左向右，于是我們首先確定第n個(gè)物品是否可以被裝入背包： if v(n)<=j f(n,j)=w(n) ; els

6、e f(n,j)=0; 在通過(guò)遞歸公式fij=maxfi+1j,fi+1j-vi+wi逐個(gè)求解出接下來(lái)的解，最后將這些局部最優(yōu)解填入表格中：由表格中的數(shù)據(jù)我們不難發(fā)現(xiàn)能夠裝入背包的最大價(jià)值，那么，接下來(lái)我們根據(jù)這個(gè)表求解出這個(gè)最大價(jià)值是由哪集中物品裝入而得到的：%3、找出裝入背包的所有物品 j=c; for i=1:n-1 if f(i,j)=f(i+1,j) t(i)=0; else t(i)=1; j=j-v(i); end end if f(n,j)=0 t(n)=0; else t(n)=1; end t于是我們就可以得到這個(gè)最優(yōu)解的“路徑”：六模型的評(píng)價(jià)與推廣不得不說(shuō)KP問(wèn)題是一個(gè)經(jīng)

7、典的動(dòng)態(tài)規(guī)劃模型，它既簡(jiǎn)單形象容易理解，又在某種程度上揭示動(dòng)態(tài)規(guī)劃的本質(zhì)。有多種方法可以處理它，比如分支限界法、回溯法、貪心算法等等都可以對(duì)其進(jìn)行求解，在這里我們僅選擇其中的動(dòng)態(tài)規(guī)劃，以實(shí)例的形式對(duì)其求解。七參考文獻(xiàn)王曉東-算法設(shè)計(jì)與分析(第三版)-清華大學(xué)出版社樂(lè)經(jīng)良、向隆萬(wàn)、李世棟-數(shù)學(xué)實(shí)驗(yàn)-高等教育出版社八附件Matlab文件基于MATLAB的0-1背包問(wèn)題的動(dòng)態(tài)規(guī)劃求解源代碼：>> c=15; % 定義背包的最大容量 v= 2 3 6 4 7; % 定義各個(gè)物品的體積 w= 10 5 8 16 9; % 定義各個(gè)物品對(duì)應(yīng)的價(jià)值 n =length(v); % n為物品的數(shù)量

8、 f=; %定義一個(gè)用于狀態(tài)交換的矩陣 t=; %用于輸出物品是否裝入背包的狀態(tài) %1、判斷第一個(gè)物品放或不放for j=1:15 if v(n)<=j f(n,j)=w(n) ; else f(n,j)=0; end end %2、判斷下一個(gè)物品是否裝入。引用遞歸公式fii=maxfi-1j,fi-1j-vi+wi for i=n-1:-1:1 for j=1:15 if j<=v(i) f(i,j)=f(i+1,j); else if f(i+1,j)>f(i+1,j-v(i)+w(i) f(i,j)=f(i+1,j); else f(i,j)=f(i+1,j-v(i)+w(i); end end end end f%3、找出裝入背包的所有物品 j=c; for