1. u1=c
2. m=n+1時，fm（u）恒為0
3. u<=0時，fm（u）為0
狀態轉移方程為u（k+1）=uk-xk*wk。
動態規劃基本方程為：wm>u時，fm（u）=f（m+1）（u），否則fm（u）為f（m+1）（u與f（m+1）（u-wm）+pm中的較大者。
定義（n+1）*c矩陣f，其m行u列處為fm（u）；（n+1）*c矩陣x，其m行u列處為剩餘容量為u，剩餘物品編號為m到n時xm的取值。
%n，c，w，p的值是自定義的
n=6;
c=10;
w=[1,2,3,4,5,6];
p=[6,5,4,3,2,1];
cishu=0;
tic;
f=zeros(n+1,c);
x=zeros(n+1,c);
y=zeros(1,n);
for m=n:-1:1
for u=1:c
if w(m)>u
f(m,u)=f(m+1,u);x(m,u)=0;
cishu=cishu+3;
elseif w(m)if f(m+1,u)>(f(m+1,u-w(m))+p(m))
f(m,u)=f(m+1,u);x(m,u)=0;
cishu=cishu+4;
elseif f(m+1,u)<(f(m+1,u-w(m))+p(m))
f(m,u)=f(m+1,u-w(m))+p(m);x(m,u)=1;
cishu=cishu+4;
else
f(m,u)=f(m+1,u);x(m,u)=-1;
cishu=cishu+4;
end else
if f(m+1,u)>p(m)
f(m,u)=f(m+1,u);x(m,u)=0;
cishu=cishu+4;
elseif f(m+1,u)f(m,u)=p(m);x(m,u)=1;
cishu=cishu+4;
else
f(m,u)=f(m+1,u);x(m,u)=-1;
cishu=cishu+4;
end end
endendt=toc
cishu
%以下迴圈是根據x矩陣取出乙個最優解
for i=1:n
u=abs(y)*w';
if c>u
y(i)=x(i,c-u);
else
y(i)=0;
endendmax=f(1,c)
y本例輸出為
t = 1.1769e-004
cishu =225
max =18
y =1 1 1 1 0 0
t表示運算時間，cishu表示比較、賦值操作的次數，max表示最大價值，y的i分量表示i物品的取捨，0表示不放入揹包，1表示放入揹包，-1表示都可以。（輸出的y只給出了一種可能的結果。改變給y賦值的那個迴圈中指標i的變化方式，可以得到其他可能的結果）
複雜度分析：演算法的實現部分在於二重for迴圈。共有n*c次迴圈，最壞情形下，每次迴圈需要2次比較，2次賦值，7次加減（由於既有指標加1，又有矩陣係數的加法，所以以上程式沒有統計加減次數），所以總運算次數不超過11*n*c，即其複雜度為o（n*c）。
[1] 王樂, 王世卿, 張靜樂. 基於 matlab 的 0—1 揹包問題的動態規劃方法求解[j]. 計算機技術與發展, 2006, 16(4): 88-89.
[2] 郭曉暉. 遺傳演算法在求解揹包問題中的應用[j]. 大連鐵道學院學報, 2001, 22(3): 32-35.
[3] 黃波, 蔡之華. 0/1 揹包問題及其解法研究[j]. 電腦知識與技術: 學術交流, 2007 (4): 229-231.
[4] martello s, toth p. knapsack problems[m]. new york: wiley, 1990.
[5] toth p. dynamic programming algorithms for the zero-one knapsack problem[j]. ***puting, 1980, 25(1):
29-45.
動態規劃演算法
首先，我們來觀察一下這個演算法。在求從b1到e的最短距離的時候，先求出從c2到e的最短距離 而在求從b2到e的最短距離的時候，又求了一遍從c2到e的最短距離。也就是說，從c2到e的最短距離我們求了兩遍。同樣可以發現，在求從c1 c2到e的最短距離的過程中，從d1到e的最短距離也被求了兩遍。而在整個程...
5動態規劃演算法習題答案
1 最大子段和問題 給定整數序列，求該序列形如的子段和的最大值 1 已知乙個簡單演算法如下 int maxsum int n,int a,int best i,int bestj return sum 試分析該演算法的時間複雜性。2 試用分治演算法解最大子段和問題，並分析演算法的時間複雜性。3 試說...
實驗二動態規劃演算法的應用
一 實驗目的 2 二 實驗內容 2 2.1數塔問題 2 2.2 最長單調遞增子串行問題 2 三 演算法設計 2 3.1 數塔問題 2 3.1.1演算法描述 2 3.1.2 函式設計 3 3.2 最長單調遞增子串行問題 3 3.1.1演算法描述 3 3.1.2 函式設計 3 四.程式除錯及執行結果分析...