【正文】 【源代碼】program P3。時(shí)間復(fù)雜度：狀態(tài)數(shù)O(n)*轉(zhuǎn)移代價(jià)O(n)=O(n2)這個(gè)題目還要求出路徑，可以用一個(gè)輔助數(shù)組path來(lái)記錄，path[i]表示從第i個(gè)出發(fā)走到的下一個(gè)點(diǎn)的編號(hào)。設(shè)計(jì)狀態(tài)opt[i]表示以i點(diǎn)出發(fā)可以挖到最多的雷的個(gè)數(shù)。既然滿(mǎn)足最優(yōu)化原理，且無(wú)后效性，我們就可以用動(dòng)態(tài)規(guī)劃解了。那它滿(mǎn)足無(wú)后效性么？因?yàn)閳D是有向的，所以以與該頂點(diǎn)相連的點(diǎn)在往下走的路線中不包括該點(diǎn)。但是貪心給了我們啟示：從一個(gè)頂點(diǎn)出發(fā)要選擇向一個(gè)與他相連且以該點(diǎn)出發(fā)可以挖到較多雷的點(diǎn)走。但很容易想到反例：51 2 1 1 1001 1 0 00 1 00 10按照貪心答案是3，但實(shí)際上答案是101。 11【輸出樣例】1 3 4 5max=27【Hint】題目中的路徑是有向的且無(wú)環(huán)路（這是我做的改動(dòng)原題中沒(méi)有要求）。 0 1 （挖地雷的數(shù)量）【輸入樣例】510，8，4，7，61（挖地雷的順序）MAX 之間是否有通路：通Aij=1,不通Aij==0）……..AN1 A1N （表示每個(gè)地窖中埋藏的地雷數(shù)量）A12…………… . 設(shè)計(jì)一個(gè)挖地雷的方案，使某人能挖到最多的地雷。同時(shí)，給出地窖之間的連接路徑。由于不是很常見(jiàn)所以沒(méi)有固定的解題模式，到時(shí)候具體問(wèn)題具體分析。print。begininit。)。beginfor i:=1 to n doif ans[i] then write(i,39。procedure print。end。while i0 dobeginans[path[i]]:=false。end。)。if opt[total]1 thenbeginwriteln(39。halt。039。end。opt[0]:=1。beginfillchar(opt,sizeof(opt),0)。procedure main。for i:=1 to n doread(w[i])。beginread(total)。procedure init。ans:array[0..maxn] of boolean。varpath,opt:array[0..maxw] of int64。constmaxw=100010。因?yàn)檫@個(gè)問(wèn)題要求多方案時(shí)輸出1，也就是說(shuō)要輸出的方案是唯一的，這時(shí)你就不需要擔(dān)心一維狀態(tài)的正確性了，可以放心的用一維求解，但要注意只有當(dāng)前狀態(tài)沒(méi)有方案是才記錄當(dāng)前的方案，否則會(huì)把正確方案替換了?！据敵鑫募咳绻麩o(wú)解，則輸出“0”；如果有多解，則輸出“1”；否則，按照升序輸出丟失的牌的編號(hào)，相鄰兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。第二行一個(gè)整數(shù)N（1N=100），表示這副牌有多少?gòu)?。這時(shí)，xiaomengxian大聲說(shuō)：“你們看我的吧！”于是他拿出筆記本電腦，編出了一個(gè)程序，很快就把缺少的牌找了出來(lái)?！贝蠹叶加X(jué)得這個(gè)辦法不錯(cuò)，于是稱(chēng)出剩下的牌的總重量，開(kāi)始計(jì)算少了哪些牌。于是這副牌的主人得意地說(shuō)：“這是一幅特制的牌，我知道整副牌每一張的重量。xiaomengxian不會(huì)打牌，只好坐在一邊看著。看到這里覺(jué)得頭暈就上趟廁所，返回來(lái)看下面的例題：例題12 新年趣事之打牌 來(lái)源：既然這樣是不是我們就應(yīng)該屏棄二維狀態(tài)解法呢？由于一維狀態(tài)在求解方案是存在錯(cuò)誤，所以二維狀態(tài)還是很有用啊。這也正是我要說(shuō)的下面的問(wèn)題；背包問(wèn)題一維狀態(tài)于二維狀態(tài)的優(yōu)劣：顯然，一維狀態(tài)的維數(shù)少空間復(fù)雜度低。顯然這個(gè)方案是真確的，所以最優(yōu)解正確。 3二維狀態(tài)求解過(guò)程： （略）可以看到一維狀態(tài)的最優(yōu)解是正確的，但細(xì)心分析發(fā)現(xiàn)一個(gè)驚人的問(wèn)題： 2 3 3 3 13 12 10 0 2 0path[0..6]=0 0 3 {記錄最后裝入包中的物品的編號(hào)}i=2opt[0..6]=1 0 0 0path[0..6]=0 0 0 (枚舉物品)opt[0..6]= 1 9一維狀態(tài)求解過(guò)程：i=1 : 1 10物品2： 3下面看這樣一個(gè)數(shù)據(jù)：載重：6 物品個(gè)數(shù)：3重量end.背包問(wèn)題方案的求法：和大多數(shù)DP問(wèn)題的方案的求法一樣，增加一個(gè)數(shù)組path和狀態(tài)維數(shù)相同用來(lái)記錄當(dāng)前狀態(tài)的決策就OK了。main。end。beginwriteln(opt[n])。end。opt[0]:=1。vari,j:longint。end。for i:= 1 to v doread(a[i])。rewrite(output)。reset(input)。vari:longint。v,n:longint。vara:array[0..maxv] of longint。maxv=100。fout=39。constfin=39。復(fù)雜度與原模型相同。對(duì)與第一個(gè)問(wèn)題，只要把原來(lái)BOOLEAN型的狀態(tài)改為INT64，在遞推過(guò)程中累加方案數(shù)即可?！据敵鑫募繂为?dú)的一行包含那個(gè)可能的構(gòu)造的方案數(shù)。要構(gòu)造的數(shù)量錢(qián)是 N (1= N=10,000)。保證總數(shù)將會(huì)適合long long (C/C++) 和 Int64 (Free Pascal)。舉例來(lái)說(shuō), 使用一個(gè)貨幣系統(tǒng) {1,2,5,10,...}產(chǎn)生 18單位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。傳統(tǒng)地，一個(gè)貨幣系統(tǒng)是由1,5,10,20 或 25,50, 和 100的單位面值組成的。end.上面提到的幾個(gè)例題都是最基礎(chǔ)的題目，而且把問(wèn)題抽象后就與背包問(wèn)題的基本模型一樣了，但有些題目用到了基本模型，要求的解卻不一定很模型一樣，下面看個(gè)例子：例題11 Money Systems () 來(lái)源：USACO 【問(wèn)題描述】母牛們不但創(chuàng)建了他們自己的政府而且選擇了建立了自己的貨幣系統(tǒng)。main。end。beginwriteln((ans1)*10)。end。ans:=max(ans,opt[i])。if (iv[j]v[q2[j]]=0) and (opt[iv[j]v[q2[j]]]0) thenopt[i]:=max(opt[i],opt[iv[j]v[q2[j]]]+v[j]*p[j]+v[q2[j]]*p[q2[j]])。for j:=1 to m dofor i:=n downto v[j] doif q[j]=0 thenbeginif (iv[j]=0) and (opt[iv[j]]0) thenopt[i]:=max(opt[i],opt[iv[j]]+v[j]*p[j])。beginfillchar(opt,sizeof(opt),0)。procedure main。exit(y)。function max(x,y:longint):longint。close(input)。q1[q[i]]:=i。v[i]:=v[i] div 10。fillchar(q2,sizeof(q2),0)。n:=n div 10。rewrite(output)。reset(input)。vari,x:longint。opt:array[0..maxn] of longint。varn,m,ans:longint。maxn=3200。fout=39。constfin=39。但在輸出是要注意將解減1。這樣opt[i]0說(shuō)明花i元可以買(mǎi)到物品。 （買(mǎi)主件和那兩個(gè)附件）設(shè)計(jì)一個(gè)狀態(tài)opt[i]表示花i元錢(qián)可買(mǎi)到的物品的價(jià)格個(gè)重要度最大值。 （買(mǎi)主件和第二個(gè)附件）W4=v[i]+v[q1[i]]+v[q2[i]] （買(mǎi)主件和第一個(gè)附件）W3=v[i]+v[q2[i]]而主件的花費(fèi)就有4種情況了。由于題目沒(méi)有直接給出每個(gè)主件對(duì)應(yīng)的附件，所以還需要做一個(gè)預(yù)處理：另開(kāi)兩個(gè)數(shù)組q1，q2來(lái)分別記錄對(duì)應(yīng)的第i個(gè)主件的附件。 標(biāo)準(zhǔn)算法因?yàn)檫@道題是典型的背包問(wèn)題，顯然標(biāo)準(zhǔn)算法就是動(dòng)態(tài)規(guī)劃。但這并不影響解題，由于附件最多兩個(gè)，那么我們做一個(gè)對(duì)主，附件做個(gè)捆綁就行了。如果q=0，表示該物品為主件，如果q0，表示該物品為附件，q是所屬主件的編號(hào)）【輸出文件】，為不超過(guò)總錢(qián)數(shù)的物品的價(jià)格與重要度乘積的總和的最大值（200000）。 p m （其中N（32000）表示總錢(qián)數(shù)，m（60）為希望購(gòu)買(mǎi)物品的個(gè)數(shù)。（其中*為乘號(hào)）請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿(mǎn)足要求的購(gòu)物單。他希望在不超過(guò)N元（可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。于是，他把每件物品規(guī)定了一個(gè)重要度，分為5等：用整數(shù)1~5表示，第5等最重要。附件不再有從屬于自己的附件。今天一早，金明就開(kāi)始做預(yù)算了，他把想買(mǎi)的物品分為兩類(lèi)：主件與附件，附件是從屬于某個(gè)主件的，下表就是一些主件與附件的例子：主件附件電腦打印機(jī)，掃描儀書(shū)柜圖書(shū)書(shū)桌臺(tái)燈，文具工作椅z無(wú)如果要買(mǎi)歸類(lèi)為附件的物品，必須先買(mǎi)該附件所屬的主件。end.例題10 金明的預(yù)算方案 () 來(lái)源：NOIP2006 第二題【問(wèn)題描述】金明今天很開(kāi)心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專(zhuān)用的很寬敞的房間。main。end。for i:=1 to n doif opt[i]ans thenans:=opt[i]。vari,ans:longint。end。end。opt[0]:=1。vari,j:longint。end。beginreadln(n,m)。procedure init。v,p:array[0..maxm] of longint。maxm=30?！驹创a】program p2。（很饒口?。?。m（其中N（30000）表示總錢(qián)數(shù)，m(25)為希望購(gòu)買(mǎi)物品的個(gè)數(shù)。他希望在不超過(guò)N 元（可以等于N 元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。于是，他把每件物品規(guī)定了一個(gè)重要度，分為5 等：用整數(shù)1~5 表示，第5 等最重要。更讓他高興的是，媽媽昨天對(duì)他說(shuō)：“你的房間需要購(gòu)買(mǎi)哪些物品，怎么布置，你說(shuō)了算，只要不超過(guò)N 元錢(qián)就行”。print。begininit。close(output)。procedure print。for i:=1 to t doif opt[i]ans then ans:=opt[i]。for i:=1 to n dofor j:=t downto w[i] doif (opt[jw[i]]0) and (opt[jw[i]]+v[i]opt[j]) thenopt[j]:=opt[jw[i]]+v[i]。beginfillchar(opt,sizeof(opt),0)。procedure main。close(input)。readln(t,n)。assign(output,fout)。beginassign(input,fin)。procedure init。w,v:array[0..maxn] of longint。maxn=110。39。39。end.【源代碼2】 {一維狀態(tài)}program medic。main。end。beginwriteln(opt[n,t])。end。beginfillchar(opt,sizeof(opt),0)。procedure main。beginif xy then max:=xelse max:=y。end。for i:=1 to n doread(w[i],v[i])。rewrite(output)。reset(input)。vari:longint。t,n:longint。varopt:array[0..maxn,0..maxt] of longint。maxt=1010。fout=39。constfin=39。【問(wèn)題分析】這是一道典型的0/1背包問(wèn)題，把時(shí)間看做標(biāo)準(zhǔn)模型中的重量，把規(guī)定的時(shí)間看做載重為T(mén)的背包，這樣問(wèn)題和基本模型就一樣了，具體實(shí)現(xiàn)這里不多說(shuō)了?！据敵鑫募浚@一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間內(nèi)，可以采到的草藥的最大總價(jià)值?！比绻闶浅匠?，你能完成這個(gè)任務(wù)嗎？【輸入文件】（1 = T = 1000）和M（1 = M = 100），用一個(gè)空格隔開(kāi)，T代表總共能夠用來(lái)采藥的時(shí)間，M代表山洞里的草藥的數(shù)目。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。 (0i=s)時(shí)間復(fù)雜度：階段數(shù)O(S)*狀態(tài)數(shù)（O(N)）*轉(zhuǎn)移代價(jià)（O(1)）=O（SN）下面看幾個(gè)例題：例題8 采藥 () 來(lái)源：NOIP2005（普及組） 第三題【問(wèn)題描述】辰辰是個(gè)天資聰穎的孩子，他的夢(mèng)想是成為世界上最偉大的醫(yī)師。邊界條件：opt[0]=1。對(duì)于第i個(gè)物品，只要opt[jw[i]]可以裝滿(mǎn)且opt[jw[i]]+v[i]比opt[j]大就裝上這個(gè)物品（更新opt[j]）。這樣問(wèn)題就解決了。總結(jié)一下上面的思維過(guò)程：放寬約束讓我們找到問(wèn)題的突破口——和背包問(wèn)題簡(jiǎn)化版一樣，我們可以卻定載重為S的背包是否可以裝滿(mǎn)。那么裝不滿(mǎn)怎么辦呢？其實(shí)裝不滿(mǎn)背包，它總要達(dá)到一定的重量（X）。那簡(jiǎn)化版的求解對(duì)我們有何啟示呢？再一次增