01背包問題
壹個旅行者有壹個最多能用m公斤的背包，現在有n件物品，它們的重量分別是W1，W2，...,Wn,它們的價值分別為C1,C2,...,Cn.若每種物品只有壹件求旅行者能獲得最大總價值。
<1>分析說明:
顯然這個題可用深度優先方法對每件物品進行枚舉(選或不選用0,1控制).
程序簡單,但是當n的值很大的時候不能滿足時間要求，時間復雜度為O（2n）。按遞歸的思想我們可以把問題分解為子問題,使用遞歸函數
設 f(i，x)表示前i件物品，總重量不超過x的最優價值
則 f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x））
f（n，m）即為最優解，邊界條件為f（0，x）＝0 ，f(i,0)=0;
動態規劃方法(順推法)程序如下:
程序如下：
program knapsack02;
const maxm=200;maxn=30;
type ar=array[1..maxn] of integer;
var m,n,j,i:integer;
c,w:ar;
f:array[0..maxn,0..maxm] of integer;
function max(x,y:integer):integer;
begin
if x>y then max:=x else max:=y;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
for i:=1 to m do f(0,i):=0;
for i:=1 to n do f(i,0):=0;
for i:=1 to n do
for j:=1 to m do
begin
if j>=w[i] then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])
else f[i,j]:=f[i-1,j];
end;
writeln(f[n,m]);
end.