要構造的面值是n(1≤n≤10,000)；
第1行:二個整數，v和n；
第2..v+1行：可用的貨幣v個整數(每行乙個)。
【輸出格式】
單獨的一行包含那個可能的構造的方案數。
【輸入樣例】
3 1012
5【輸出樣例】
10[分析]：此題是個揹包模型，只是問題的解是構造方案數,設w[j]為第j種幣值，狀態f[i]：構造面值為i時可能的方案數，則狀態轉移方程為：
f[i]:=∑f[i-w[j]]，i>=w[j],邊界：f[0]:
=1;f[n]即為問題的解。
注意：由於此題的資料規模比較大，所以要用到高精度加法，估計最大的資料可以達到73位，為節約程式時間和空間效率，還採用了萬進製的高精度加法。參考程式
如下：var
f:array[0..10000,1..20]of integer;
long:array[0..10000]of integer;//儲存位數
w:array[0..25]of integer;
n,m,i,j,k:integer;
procedure add(r,t:integer);//萬進製高精度加
var i,k:integer;
begin
if long[t]k:=0;
for i:=1 to long[t] do
begin
f[t,i]:=(f[t,i]+f[r,i]+k);
k:=f[t,i] div 10000;//每乙個存4位,萬進製，這樣省時省空間
f[t,i]:=f[t,i] mod 10000;
end;
while k>0 do //進製處理
begin
inc(long[t]);
f[t,long[t]]:=k mod 10000;
k:=k div 10000;
end;
end;
procedure main;
var i,j:integer;
begin
f[0,1]:=1; long[0]:=1;
for i:=1 to m do
for j:=w[i] to n do add(j-w[i],j);
write(f[n,long[n]]);//輸出答案,由於每個存4位,所以有時需要補零
for i:=long[n]-1 downto 1 do
begin
if f[n,i]<10 then write('000')
else if f[n,i]<100 then write('00')
else if f[n,i]<1000 then write('0');
write(f[n,i]);
end;
end;
begin
assign(input,'money.in');reset(input); assign(output,'money.out');rewrite(output);
readln(m,n);
for i:=1 to m do readln(w[i]);
main;
close(input);close(output);
end.
（二）、資源分配模型
資源分配模型的動態規劃，這型別的題目一般是：給定m個資源，分配給n個部門，第i個部門獲得j個資源有個盈利值，問如何分配這m個資源能使獲得的盈利最大，求最大盈利。這型別的題目一般用資源數做狀態，陣列f[i,j]表示前個i個部門分配j個資源的最大盈利，則狀態轉移方程為：
f[i,j]:=max (0<=k<=j)
程式框架如下：
var i,j,k:longint;
begin
for i:=1 to n do
for j:=0 to m do
for k:=0 to j do
if f[i-1,k]+value[i,j-k]>f[i,j] then f[i,j]:=f[i-1,k]+value[i,j-k];
writeln(f[n,m]);
end;
資源分配型別典型應用是花店櫥窗(flower.pas)設定，沒做過的同學可以自己去練習一下，下面的乙個例題，也是此型別的轉換。
[問題描述]
農夫ion放完馬以後，需要把馬兒關回馬廄。為了做好這件事，ion讓馬排成一行跟著他入馬廄。他想出了乙個就近入廄的辦法：
讓前p1匹馬進入第乙個馬廄，然後的p2匹馬進入第二個馬廄，如此類推。而且，他不想讓任何乙個馬廄（共k個）留空，還有所有的馬都進入馬廄。
已知ion只有黑色和白色兩種顏色的馬，然而並不是所有的馬都能相處融洽。假如有i匹黑馬和j匹白馬同在乙個馬廄，那麼它們之間的不愉快係數為i*j。馬廄總的不愉快係數等於k個馬廄的不愉快係數之和。
請幫忙把n匹馬按順序放入k個馬廄中（即求一種 p1,p2…的安排方案），使得總的不愉快係數最小。
[輸入格式]
輸入第一行為乙個n和k；（n<=100,k<=n）;
輸入第二行為n個數0和1，0表示白馬，1表示黑馬
[輸出格式]
一行，最小的不愉快係數。
樣例輸入
3 21 0 1
樣例輸出
1分析：設f[i,j]：表示將前i匹馬放入前j個馬廄，得到的最小不愉快係數。w[i,j]：表示將第i至第j匹馬放入同乙個馬廄所得到的不愉快係數。
狀態轉移方程為：f[i,j]=min(f[k,j-1]+w[k+1,i])(i目標狀態為：f[1,n]
但我們可以發現,由於這裡為乘積之和，在輸入資料較大時有可能超過長整形甚至實形的範圍，所以我們還需用高精度計算，但這是基本功，程式中就沒有寫了，請讀者自行完成。
參考程式
vars:array[1..50] of integer;
f:array[1..50,1..50] of ***p;
d:array[1..50,1..50] of byte;
n:integer;
procedure init;
var i:integer;
begin
readln(n);
for i:=1 to n do read(s[i]);
end;
procedure dp;//動態規劃
var i,j,k:integer;
begin
for i:=1 to n do
for j:=i+1 to n do f[i,j]:=maxlongint;//賦初始值
for i:=n-2 downto 1 do
for j:=i+2 to n do
for k:=i+1 to j-1 do
if (f[i,j]>f[i,k]+f[k,j]+s[i]*s[j]*s[k]) then
begin
f[i,j]:=f[i,k]+f[k,j]+s[i]*s[j]*s[k];
d[i,j]:=k; //記錄父節點
end;
end;
procedure print(i,j:integer);//輸出每個三角形
begin
if j=i+1 then exit;
write(',',i,' ',j,' ',d[i,j]);
out(i,d[i,j]);
out(d[i,j],j);
end;
procedure out;//輸出資訊
begin
writeln('the minimum is :',f[1,n]:0:0);
writeln('the formation of ',n-2,' ********:');
第4講動態規劃
我們先來看乙個簡單的多階段決策問題。現有一張地圖，各結點代表城市，兩結點間連線代表道路，線上數字表示城市間的距離。如圖1所示，試找出從結點1到結點10的最短路徑。第一階段第二階段第三階段第四階段第五階段 圖1本問題的解決可採用一般的窮舉法，即把從結點1至結點10的所有道路列舉出來，計算其長度，再進行...
4種常見姿態禮儀
站姿禮儀 站立是人最基本的姿勢，是一種靜態的美。站立時，身體應與地面垂直，重心放在兩個前腳掌上，挺胸 收腹 收頒 抬頭 雙肩放鬆。雙臂自然下垂或在體前交叉，眼睛平視，面帶笑容。站立時不要歪脖 斜腰 曲腿等，在一些正式場合不宜將手插在褲袋裡或交叉在胸前，更不要下意識地做些小動作，那樣不但顯得拘謹，給人...
國際交易的動態模型
周一五六七節 每 本部 本部群 1 5 1 15 趙麗霞60 0周一九十十一節 每週 1 5周 本部 本部嘉五105 1 5 1 15鄭建軍15 0人力資源管理專題 周 1 5周 二102 周二二三四 本部 本部群 1 5 1 15 龔曉華10 0投資學原理節 每 周 1 5周 二102 周五五六七...