【正文】 t[i],opt[iv[j]v[q2[j]]]+v[j]*p[j]+v[q2[j]]*p[q2[j]])。if (iv[j]v[q1[j]]v[q2[j]]=0) and (opt[iv[j]v[q1[j]]v[q2[j]]]0) thenopt[i]:=max(opt[i],opt[iv[j]v[q1[j]]v[q2[j]]]+v[j]*p[j]+v[q1[j]]*p[q1[j]]+v[q2[j]]*p[q2[j]])。ans:=max(ans,opt[i])。end。end。procedure print。beginwriteln((ans1)*10)。close(output)。end。begininit。main。print。end.上面提到的幾個例題都是最基礎(chǔ)的題目，而且把問題抽象后就與背包問題的基本模型一樣了，但有些題目用到了基本模型，要求的解卻不一定很模型一樣，下面看個例子：例題11 Money Systems () 來源：USACO 【問題描述】母牛們不但創(chuàng)建了他們自己的政府而且選擇了建立了自己的貨幣系統(tǒng)。[In their own rebellious way],，他們對貨幣的數(shù)值感到好奇。傳統(tǒng)地，一個貨幣系統(tǒng)是由1,5,10,20 或 25,50, 和 100的單位面值組成的。母牛想知道有多少種不同的方法來用貨幣系統(tǒng)中的貨幣來構(gòu)造一個確定的數(shù)值。舉例來說, 使用一個貨幣系統(tǒng) {1,2,5,10,...}產(chǎn)生 18單位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。寫一個程序來計算有多少種方法用給定的貨幣系統(tǒng)來構(gòu)造一定數(shù)量的面值。保證總數(shù)將會適合long long (C/C++) 和 Int64 (Free Pascal)?！据斎胛募控泿畔到y(tǒng)中貨幣的種類數(shù)目是 V (1= V=25)。要構(gòu)造的數(shù)量錢是 N (1= N=10,000)。第 1 行: 二整數(shù)， V 和 N第 2 行： 可用的貨幣 V 個整數(shù)?！据敵鑫募繂为毜囊恍邪莻€可能的構(gòu)造的方案數(shù)?！据斎霕永? 101 2 5【輸出樣例】10【問題分析】把錢面值，把要構(gòu)造的前看做載重為N的背包，這個問題便是0/1背包的簡化版了，但這個問題和傳統(tǒng)模型有所差異，不是判斷N是否可構(gòu)成，而是求構(gòu)成N的方案，而且這里的面值是可以重復(fù)利用的（你可以看做是物品有無限多）。對與第一個問題，只要把原來BOOLEAN型的狀態(tài)改為INT64，在遞推過程中累加方案數(shù)即可。對于第二個問題，基本模型中為了避免重復(fù)在內(nèi)重循環(huán)枚舉背包載重時采用倒循環(huán)，現(xiàn)在只要正向循環(huán)就OK了。復(fù)雜度與原模型相同。【源代碼】{ID:hhzhaojia2PROG:moneyLANG:PASCAL}program money。constfin=39。39。fout=39。39。maxv=100。maxn=10010。vara:array[0..maxv] of longint。opt:array[0..maxn] of int64。v,n:longint。procedure init。vari:longint。beginassign(input,fin)。reset(input)。assign(output,fout)。rewrite(output)。read(v,n)。for i:= 1 to v doread(a[i])。close(input)。end。procedure main。vari,j:longint。beginfillchar(opt,sizeof(opt),0)。opt[0]:=1。for i:=1 to v dofor j:=a[i] to n doinc(opt[j],opt[ja[i]])。end。procedure print。beginwriteln(opt[n])。close(output)。end。begininit。main。print。end.背包問題方案的求法：和大多數(shù)DP問題的方案的求法一樣，增加一個數(shù)組path和狀態(tài)維數(shù)相同用來記錄當(dāng)前狀態(tài)的決策就OK了。輸出方案時候通過當(dāng)前決策推出上一決策，這一連穿的決策序列就是要求的方案。下面看這樣一個數(shù)據(jù)：載重：6 物品個數(shù)：3重量 價值物品1： 3 10物品2： 2 2物品3： 1 9一維狀態(tài)求解過程：i=1 : (枚舉物品)opt[0..6]= 1 0 0 11 0 0 0path[0..6]=0 0 0 1 0 0 0 {記錄最后裝入包中的物品的編號}i=2opt[0..6]=1 0 3 11 0 13 0path[0..6]=0 0 2 1 0 2 0i=3opt[0..6]=1 10 3 12 20 13 22path[0..6]=0 3 2 3 3 2 3二維狀態(tài)求解過程： （略）可以看到一維狀態(tài)的最優(yōu)解是正確的，但細(xì)心分析發(fā)現(xiàn)一個驚人的問題： 方案不對??！什么最優(yōu)解正確而方案不正確呢？因為在解i=3時opt[6]用到的方案數(shù)應(yīng)該是9+2+10=21。顯然這個方案是真確的，所以最優(yōu)解正確。但是求解完opt[6]后，接著求解opt[3]卻把原來的opt[3]=10改成了opt[3]=2+9=11這樣，在整個求解過程結(jié)束后最后的方案opt[6]=9+2+10就變成了opt[6]=9+2+2+9也就是說1，2兩個物品裝了兩次。這也正是我要說的下面的問題；背包問題一維狀態(tài)于二維狀態(tài)的優(yōu)劣：顯然，一維狀態(tài)的維數(shù)少空間復(fù)雜度低。甚至在一些問題上可以減輕思考負(fù)擔(dān)。既然這樣是不是我們就應(yīng)該屏棄二維狀態(tài)解法呢？由于一維狀態(tài)在求解方案是存在錯誤，所以二維狀態(tài)還是很有用啊。當(dāng)然有些問題雖然也是在求解方案但要求方案唯一這樣就又可以用一維狀態(tài)了?？吹竭@里覺得頭暈就上趟廁所，返回來看下面的例題：例題12 新年趣事之打牌 來源： vijos P1071【問題描述】過年的時候，大人們最喜歡的活動，就是打牌了。xiaomengxian不會打牌，只好坐在一邊看著。這天，正當(dāng)一群人打牌打得起勁的時候，突然有人喊道：“這副牌少了幾張！”眾人一數(shù)，果然是少了。于是這副牌的主人得意地說：“這是一幅特制的牌，我知道整副牌每一張的重量。只要我們稱一下剩下的牌的總重量，就能知道少了哪些牌了?！贝蠹叶加X得這個辦法不錯，于是稱出剩下的牌的總重量，開始計算少了哪些牌。由于數(shù)據(jù)量比較大，過了不久，大家都算得頭暈了。這時，xiaomengxian大聲說：“你們看我的吧！”于是他拿出筆記本電腦，編出了一個程序，很快就把缺少的牌找了出來。如果是你遇到了這樣的情況呢？你能辦到同樣的事情嗎？【輸入文件】第一行一個整數(shù)TotalW，表示剩下的牌的總重量。第二行一個整數(shù)N（1N=100），表示這副牌有多少張。接下來N行，每行一個整數(shù)Wi（1=Wi=1000），表示每一張牌的重量?！据敵鑫募咳绻麩o解，則輸出“0”；如果有多解，則輸出“1”；否則，按照升序輸出丟失的牌的編號，相鄰兩個數(shù)之間用一個空格隔開。【輸入樣例】2704100110170200【輸出樣例】2 4【提交鏈接】【問題分析】如果你認(rèn)真的做了前面的題，把這個題目抽象成背包問題對你來說應(yīng)該易如反掌了，我就不多說了。因為這個問題要求多方案時輸出1，也就是說要輸出的方案是唯一的，這時你就不需要擔(dān)心一維狀態(tài)的正確性了，可以放心的用一維求解，但要注意只有當(dāng)前狀態(tài)沒有方案是才記錄當(dāng)前的方案，否則會把正確方案替換了?！驹创a1】program P1071。constmaxw=100010。maxn=110。varpath,opt:array[0..maxw] of int64。w:array[0..maxn] of longint。ans:array[0..maxn] of boolean。n,total:longint。procedure init。vari:longint。beginread(total)。read(n)。for i:=1 to n doread(w[i])。end。procedure main。vari,j:longint。beginfillchar(opt,sizeof(opt),0)。fillchar(ans,sizeof(ans),true)。opt[0]:=1。for i:=1 to n dofor j:=total downto w[i] doif opt[jw[i]]0 thenbeginif opt[j]=0 thenpath[j]:=i。{只有當(dāng)前狀態(tài)沒求過才記錄方案}inc(opt[j],opt[jw[i]])。end。if opt[total]=0 thenbeginwriteln(39。039。)。halt。end。if opt[total]1 thenbeginwriteln(39。139。)。halt。end。i:=total。while i0 dobeginans[path[i]]:=false。i:=iw[path[i]]。end。end。procedure print。vari:longint。beginfor i:=1 to n doif ans[i] then write(i,39。 39。)。end。begininit。main。print。end.一維動態(tài)規(guī)劃最常見的就是前面總結(jié)的最長下降/非降子序列和0/1背包問題了，當(dāng)然還有別的一寫題。由于不是很常見所以沒有固定的解題模式，到時候具體問題具體分析。下面在看一些例子：例題13 挖地雷問題 () 來源：NOIP1996（提高組）第三題（有改動）【問題描述】在一個地圖上有N個地窖（N=20），每個地窖中埋有一定數(shù)量的地雷。同時，給出地窖之間的連接路徑。如圖3圖3當(dāng)?shù)亟鸭捌溥B接的數(shù)據(jù)給出之后，某人可以從任一處開始挖地雷，然后可以沿著指出的連接往下挖（僅能選擇一條路徑），當(dāng)無連接時挖地雷工作結(jié)束。設(shè)計一個挖地雷的方案，使某人能挖到最多的地雷。【輸入文件】N： （表示地窖的個數(shù)）Ｗ1，W2，W3，……WN （表示每個地窖中埋藏的地雷數(shù)量）A12…………… . A1N 地窖之間連接路徑（其中Ａij=1表示地窖i,jA23…………..A2N 之間是否有通路：通Aij=1,不通Aij==0）……..AN1 AN【輸出文件】K1K2……….KV （挖地雷的順序）MAX （挖地雷的數(shù)量）【輸入樣例】510，8，4，7，61 1 1 00 0 01 11【輸出樣例】1 3 4 5max=27【Hint】題目中的路徑是有向的且無環(huán)路（這是我做的改動原題中沒有要求）?！締栴}分析】看到題目的第一影響是貪心——以一點出發(fā)找與他連接的地窖中地雷數(shù)最多的一個。但很容易想到反例：51 2 1 1 1001 1 0 00 1 00 10按照貪心答案是3，但實際上答案是101。于是就不得不放棄貪心的想法。但是貪心給了我們啟示：從一個頂點出發(fā)要選擇向一個與他相連且以該點出發(fā)可以挖到較多雷的點走。（有點拗口）另一種解釋：如果一個頂點連同N個分量，顯然要則一個較大的就是問題的解答，這個定義是滿足最優(yōu)化原理的。那它滿足無后效性么？因為圖是有向的，所以以與該頂點相連的點在往下走的路線中不包括該點。也就是說圖是一個AOV網(wǎng)（有向無環(huán)圖）。既然滿足最優(yōu)化原理，且無后效性，我們就可以用動態(tài)規(guī)劃解了。這個問題的階段就是拓?fù)湫蛄?，但由于輸入是倒三角形，所以我們沒必要求拓?fù)湫蛄?，只要從N到著求解就可以了。設(shè)計狀態(tài)opt[i]表示以i點出發(fā)可以挖到最多的雷的個數(shù)。狀態(tài)轉(zhuǎn)移方程：opt[i]=max{opt[j]}+w[i] (g[i,j]=1)(g存圖，w[i]存第i個地窖中的雷的個數(shù))。時間復(fù)雜度：狀態(tài)數(shù)O(n)*轉(zhuǎn)移代價O(n)=O(n2)這個題目還要求出路徑，可以用一個輔助數(shù)組path來記錄，path[i]表示從第i個出發(fā)走到的下一個點的編號。求解完只要按path記錄的路徑輸出即可?！驹创a】program P3。cons