揹包問題：
在m件物品取出若干件放在空間為w的揹包裡，每件物品的重量為w1，w·2……wn，與之相對應的價值為p1,p2……pn。求出獲得最大價值的方案。
注意：在本題中，所有的重量值均為整數。
[演算法分析]：
對於揹包問題，通常的處理方法是搜尋。
用遞迴來完成搜尋，演算法設計如下：
function make( i , j:integer) :integer;
初始時i=m , j=揹包總容量
begin
if i:=0 then
make:=0;
if j>=wi then (揹包剩餘空間可以放下物品 i )
r1:=make(i-1,j-wi)+v[i]; (第i件物品放入所能得到的價值 )
r2:=make(i-1,j) (第i件物品不放所能得到的價值 )
make:=max
end;
這個演算法的時間複雜度是o(2^n)，我們可以做一些簡單的優化。
由於本題中的所有物品的重量均為整數，經過幾次的選擇後背包的剩餘空間可能會相等，在搜尋中會重複計算這些結點，所以，如果我們把搜尋過程中計算過的結點的值記錄下來，以保證不重複計算的話，速度就會提高很多。這是簡單的"以空間換時間"。
我們發現，由於這些計算過程中會出現重疊的結點，符合動態規劃中子問題重疊的性質。
同時，可以看出如果通過第n次選擇得到的是乙個最優解的話，那麼第n-1次選擇的結果一定也是乙個最優解。這符合動態規劃中最優子問題的性質。
考慮用動態規劃的方法來解決，這裡的：
階段是：在前n件物品中，選取若干件物品放入揹包中；
狀態是：在前n件物品中，選取若干件物品放入所剩空間為w的揹包中的所能獲得的最大價值；
決策是：第n件物品放或者不放；
由此可以寫出動態轉移方程：
我們用f[i,j]表示在前 i 件物品中選擇若干件放在所剩空間為 j 的揹包裡所能獲得的最大價值
f[i,j]=max
這樣，我們可以自底向上地得出在前m件物品中取出若干件放進揹包能獲得的最大價值，也就是f[m,w]
演算法設計如下：
procedure make;
begin
for i:=0 to w do
f[0,i]:=0;
for i:=1 to m do
for j:=0 to w do begin
f[i,j]:=f[i-1,j];
if (j>=w[i]) and (f[i-1,j-w[i]]+v[i]>f[i,j]) then
f[i,j]:=f[i-1,j-w[i]]+v[i];
end;
writeln(f[m,wt]);
end;
由於是用了乙個二重迴圈，這個演算法的時間複雜度是o（n*w)。而用搜尋的時候，當出現最壞的情況，也就是所有的結點都沒有重疊，那麼它的時間複雜度是o（2^n)。看上去前者要快很多。
但是，可以發現在搜尋中計算過的結點在動態規劃中也全都要計算，而且這裡算得更多（有一些在最後沒有派上用場的結點我們也必須計算），在這一點上好像是矛盾的。
事實上，由於我們定下的前提是：所有的結點都沒有重疊。也就是說，任意n件物品的重量相加都不能相等，而所有物品的重量又都是整數，那末這個時候w的最小值是：
1+2+2^2+2^3+……+2^n-1=2^n -1
此時n*w>2^n，動態規劃比搜尋還要慢~~|||||||所以，其實揹包的總容量w和重疊的結點的個數是有關的。
考慮能不能不計算那些多餘的結點……
那麼換一種狀態的表示方式：
狀態是：在前n件物品中，選取若干件物品放入所佔空間為w的揹包中的所能獲得的最大價值；
階段和決策：同上；
狀態轉移方程是：
f[i,j]=max
這樣，我們可以得出在前m件物品中取出若干件放進揹包在所佔空間不同的狀態下能獲得的最大價值，在其中搜尋出最大的乙個就是題目要求的解。
演算法設計如下：
procedure make;
begin
f[0,wt]:=0;
for i:=1 to n do
for j:=0 to w (揹包總容量) do
if f[i-1,j]未被賦過值 then （這些結點與計算無關，忽略）
continue
else
f[i,j]:=max;
最大價值：=max （求最大值）
j:=1 to w
end;
由於事實上在計算的過程中每乙個階段的狀態都只和上乙個階段有關，所以只需要來乙個兩層的陣列迴圈使用就可以了，這是動態規劃中較常使用的降低空間複雜度的方法。
本題能夠用動態規劃的乙個重要條件就是：所有的重量值均為整數因為
1）這樣我們才可以用陣列的形式來儲存狀態；
2）這樣出現子問題重疊的概率才比較大。（如果重量是實型的話，幾個重量相加起來相等的概率會大大降低）
所以，當重量不是整數的時候本題不適合用動態規劃。
[解的輸出]：
在計算最大價值的時候我們得到了一張**（f[i,j]),我們可以利用這張**輸出解。
可以知道，如果f[i-1,j+wi]+v[i]=f[i,j] (第二個演算法)，則選擇物品i放入揹包。
演算法設計1：
進行反覆的遞迴搜尋，依次輸出物品序號；
procedure out(i,j:integer);（初始時 i=n, j=獲得最大價值的物品所佔的空間）
begin
if i=0 then exit;
if f[i,j]=f[i-1,j+w[i]]+v[i] then begin
輸出解out(i-1,j+w[i]);
endelse
out(i-1,j);
end;
演算法設計2：
同樣的思路我們可以用迴圈來完成；
procedure out2;
vari,ws:integer;
begin
ws:=獲得最大價值的物品所佔的空間;
for i:=n downto 1 do begin
if (ws>=w[i]) and (f[i,ws]=f[i-1,ws-w[i]]+v[i]) then begin
輸出解；
ws:=ws-w[i];
end;
end;
writeln;
end;
用這兩種演算法的前提是我們必須存住 f[i,j] 這一整個二維陣列，但是如果用迴圈陣列的話怎樣輸出解呢？
顯然，我們只需要存住乙個布林型的二維陣列，記錄每件物品在不同的狀態下放或者不放就可以了。這樣一來陣列所佔的空間就會大大降低。
[解題收穫]：
1）在動態程式設計中，狀態的表示是相當重要的，選擇正確的狀態表示方法會直接影響程式的效率。
2）針對題目的不同特點應該選擇不同的解題策略，往往能夠達到事半功倍的效果。像本題就應該把握住"所有的重量值均為整數"這個特點。
揹包問題全攻略
揹包問題全攻略
部分揹包問題可有貪心法求解：計算piwi
資料結構：
w[i]第i個揹包的重量；
p[i]第i個揹包的價值；
(1)每個揹包只能使用一次或有限次(可轉化為一次)：
a.求最多可放入的重量。
noip2001 裝箱問題
有乙個箱子容量為v(正整數，o≤v≤20000)，同時有n個物品(o≤n≤30)，
每個物品有乙個體積 (正整數)。
要求從 n 個物品中，任取若千個裝入箱內，使箱子的剩餘空間為最小。
l 搜尋方法
procedure search(k,vinteger);
var i,jinteger;
begin
if v best then best=v;
if v-(s[n]-s[k-1]) =best then exit;
if k =n then begin
if v w[k] then search(k+1,v-w[k]);
search(k+1,v);
end;
end;
l dp
f[i,j]為前i個物品中選擇若干個放入使其體積正好為j的標誌，為布林型。
實現將最優化問題轉化為判定性問題
f[i,j]=f[i-1,j-w[i]] (w[i] =j =v) 邊界：f[0,0]=true.
for i=1 to n do
for j=w[i] to v do f[i,j]=f[i-1,j-w[i]];
優化：當前狀態只與前一階段狀態有關，可降至一維。
f[0]=true;
for i=1 to n do begin
f1=f;
for j=w[i] to v do
if f[j-w[i]] then f1[j]=true;
f=f1;
end;
b.求可以放入的最大價值。
c.求恰好裝滿的情況數。
(2)每個揹包可使用任意次：
a.求最多可放入的重量。
狀態轉移方程為
f[i,j]=max (0 =k = i div w[j])
其中f[i,j]表示容量為i時取前j種揹包所能達到的最大值。
優化：begin
fillchar(problem,sizeof(problem),0);
assign(input,'inflate.in');
reset(input);
readln(m,n);
for i=1 to n do
with problem[i] do
readln(point,time);
close(input);
fillchar(f,sizeof(f),0);
for i=1 to m do
for j=1 to n do
if i-problem[j].time =0 then
begin
t=problem[j].point+f[i-problem[j].time];
if t f[i] then f[i]=t;
end;
assign(output,'inflate.out');
rewrite(output);
writeln(f[m]);
close(output);
end.
c.求恰好裝滿的情況數。
ahoi2001 problem2
求自然數n本質不同的質數和的表示式的數目。
思路一，生成每個質數的係數的排列，在一一測試，這是通法。
procedure try(depinteger);
var i,jinteger;
begin
cal;
if now n then exit;
if dep=l+1 then begin
cal;
if now=n then inc(tot);
exit;
end;
for i=0 to n div pr[dep] do begin
xs[dep]=i;
try(dep+1);
xs[dep]=0;
end;
end;
思路二，遞迴搜尋效率較高
procedure try(dep,restinteger);
var i,j,xinteger;
begin
if (rest =0) or (dep=l+1) then begin
if rest=0 then inc(tot);
exit;
end;
for i=0 to rest div pr[dep] do
try(dep+1,rest-pr[dep]i);
end;
思路三：可使用動態規劃求解
usaco1.2 money system
v個物品，揹包容量為n，求放法總數。
轉移方程：
procedure update;
var j,kinteger;
begin
c=a;
for j=0 to n do
if a[j] 0 then
for k=1 to n div now do
if j+nowk =n then inc(c[j+nowk],a[j]);
a=c;
end;
begin
read(now);
i=0;
while i<=n do begin
a[i]=1; inc(i,now); end;
for i=2 to v do
begin
read(now);
update;
end;
writeln(a[n]);
end.
編寫程式,用動態規劃法求解0 1揹包問題
要求 編寫程式，用動態規劃法求解0 1揹包問題。一 實驗目的與要求 1 明確0 1揹包問題的概念 2 利用動態規劃解決0 1揹包問題問題 二 實驗題 0 1揹包問題 knapsack problem 某商店有n個物品，第i個物品價值為vi，重量 或稱權值 為wi，其中vi和wi為非負數,揹包的容量為...
動態規劃法解
2011級3班張思源 動態規劃演算法原理 將待求解的問題分解成若干個相互聯絡的子問題，先求解子問題，然後從這些子問題的解得到原問題的解 對於重複出現的子問題，只在第一次遇到的時候對它進行求解，並把答案儲存起來。為了不去求解相同的子問題，引入乙個陣列，把所有子問題的解存於該陣列中，這就是動態規劃所採用...
最大欄位和問題動態規劃法
淮海工學院計算機工程學院 實驗報告書 課程名 演算法分析與設計 題目 實驗2 動態規劃演算法 最大子段和問題 班級軟體081班 學號110831116 姓名陳點點 實驗2 動態規劃演算法 實驗目的和要求 1 深刻掌握動態規劃法的設計思想並能熟練運用 2 理解這樣乙個觀點 同樣的問題可以用不同的方法解...