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

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

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

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

5、的背包可以獲得的最大價值。則其狀態(tài)轉(zhuǎn)移方程便是：fij=maxfi-1j,fi-1j-vi+wi對于第i個物品，我們可以拿這個物品的體積同背包內(nèi)剩余的體積相比較，如果背包內(nèi)剩余的容量大于物品的體積，那么這個物品就可以裝入背包，這時我們只要判斷裝入這個物品后和裝入這個物品前的價值哪一個更大，就可以通過這種遞歸的方式球的背包能裝入的最大價值。五模型建立與求解我們知道，動態(tài)規(guī)劃算法又叫填表法，填表的順序為自底向上，自左向右，于是我們首先確定第n個物品是否可以被裝入背包： if v(n)<=j f(n,j)=w(n) ; else f(n,j)=0; 在通過遞歸公式fij=maxfi+1j,fi

6、+1j-vi+wi逐個求解出接下來的解，最后將這些局部最優(yōu)解填入表格中：由表格中的數(shù)據(jù)我們不難發(fā)現(xiàn)能夠裝入背包的最大價值，那么，接下來我們根據(jù)這個表求解出這個最大價值是由哪集中物品裝入而得到的：%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于是我們就可以得到這個最優(yōu)解的“路徑”：六模型的評價與推廣不得不說KP問題是一個經(jīng)典的動態(tài)規(guī)劃模型，它既簡單形象容易理解，又在某種程度上揭示動態(tài)規(guī)劃的

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

8、入背包的狀態(tài) %1、判斷第一個物品放或不放for j=1:15 if v(n)<=j f(n,j)=w(n) ; else f(n,j)=0; end end %2、判斷下一個物品是否裝入。引用遞歸公式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