【文章內容簡介】 k+w[i]的背包就可以裝滿。于是對于一個opt[j]來說，只要opt[jw[i]]是true（表示可裝滿）那opt[j]就可以裝滿，但要注意：針對每一個物品枚舉背包的載重量時如果這樣正向的推導會使同一個物品用好幾次，因為k+w[i]可裝滿那k+w[i]+w[i]就可裝滿，但實際上是裝不滿的因為物品只有一個。解決這個問題很簡單，只要逆向推導就OK了。這樣劃分階段，設計狀態(tài)，滿足無后效性和么？顯然對與一個每一個階段都是獨立的，物品的順序并不影響求解，因為裝物品的次序不限。而對于opt[j]只考慮opt[jw[i]]而不考慮后面的，所以滿足無后效性。有了上面的分析不難寫出狀態(tài)轉移方程：opt[j]:=opt[jw[1]] {opt[jw[i]]=true}時間復雜度：階段數(shù)O(S)*狀態(tài)數(shù)（O(N)）*轉移代價（O(1)）=O（SN）下面看幾個例題：例題5 裝箱問題 () 來源：NOIP2001(普及組) 第四題【問題描述】有一個箱子容量為V（正整數(shù)，0＜＝V＜＝20000），同時有n個物品（0＜n＜＝30＝，每個物品有一個體積（正整數(shù)）。要求n個物品中，任取若干個裝入箱內，使箱子的剩余空間為最小。【輸入文件】第一 行一個正整數(shù)V表示箱子的容量，第二行一個正整數(shù)N表示物品個數(shù)，接下來N行列出這N個物品各自的體積?！据敵鑫募繂为氁恍?，表示箱子最小的剩余空間。【輸入樣例】2468312797【輸出樣例】0【問題分析】本題是經典的0/1背包問題，并且是0/1背包的簡化版，把箱子看做背包，容量看做載重量，體積看做重量，剩余空間最小也就是盡量裝滿背包。于是這個問題便成了：有一個栽重量為V的背包，有N個物品，盡量多裝物品，使背包盡量的重。設計一個狀態(tài)opt[i]表示重量i可否構成。狀態(tài)轉移方程：opt[j]:=opt[jw[l]] {opt[jw[i]]=true}最終的解就是vx（x=n 且opt[x]=true 且 opt[x+1..n]=false）?！驹创a1】program pack。constfin=39。39。fout=39。39。maxv=20010。maxn=100。varopt:array[0..maxv] of boolean。w:array[0..maxn] of longint。v,n,x:longint。procedure init。vari:longint。beginassign(input,fin)。reset(input)。assign(output,fout)。rewrite(output)。read(v)。read(n)。for i:=1 to n doread(w[i])。end。procedure main。vari,j:longint。beginfillchar(opt,sizeof(opt),false)。opt[0]:=true。for i:=1 to n dofor j:=v downto w[i] doif opt[jw[i]] then opt[j] :=true。x:=v。while not opt[x] do dec(x)。end。procedure print。beginwriteln(vx)。close(input)。close(output)。end。begininit。main。print。end.例題6 砝碼稱重 來源：NOIP1996（提高組） 第四題【問題描述】設有1g、2g、3g、5g、10g、20g的砝碼各若干枚（其總重=1000），用他們能稱出的重量的種類數(shù)。【輸入文件】a1 a2 a3 a4 a5 a6（表示1g砝碼有a1個，2g砝碼有a2個，…，20g砝碼有a6個，中間有空格）?！据敵鑫募縏otal=N（N表示用這些砝碼能稱出的不同重量的個數(shù)，但不包括一個砝碼也不用的情況）?！据斎霕永? 1 0 0 0 0【輸出樣例】TOTAL=3【問題分析】把問題稍做一個改動，已知a1+a2+a3+a4+a5+a6個砝碼的重量w[i], w[i]∈{ 1,2,3,5,10,20} 其中砝碼重量可以相等，求用這些砝碼可稱出的不同重量的個數(shù)。這樣一改就是經典的0/1背包問題的簡化版了，求解方法完全和上面說的一樣，這里就不多說了，只是要注意這個題目不是求最大載重量，是統(tǒng)計所有的可稱出的重量的個數(shù)?！驹创a1】program P4。constmaxn=1010。w:array[1..6] of longint=(1,2,3,5,10,20)。varopt:array[0..maxn] of boolean。a:array[1..6] of longint。procedure init。vari:longint。beginfor i:=1 to 6 doread(a[i])。end。procedure main。vari,j,k:longint。beginfillchar(opt,sizeof(opt),false)。opt[0]:=true。for i:=1 to 6 dofor j:=1 to a[i] dofor k:=maxn downto w[i] doif opt[kw[i]] then opt[k]:=true。end。procedure print。varans,i:longint。beginans:=0。for i:=1 to maxn doif opt[i] theninc(ans)。writeln(ans)。end。begininit。main。print。end.例題7 積木城堡 來源：vijos P1059【問題描述】XC的兒子小XC最喜歡玩的游戲用積木壘漂亮的城堡。城堡是用一些立方體的積木壘成的，城堡的每一層是一塊積木。小XC是一個比他爸爸XC還聰明的孩子，他發(fā)現(xiàn)壘城堡的時候，如果下面的積木比上面的積木大，那么城堡便不容易倒。所以他在壘城堡的時候總是遵循這樣的規(guī)則。小XC想把自己壘的城堡送給幼兒園里漂亮的女孩子們，這樣可以增加他的好感度。為了公平起見，他決定把送給每個女孩子一樣高的城堡，這樣可以避免女孩子們?yōu)榱双@得更漂亮的城堡而引起爭執(zhí)?？墒撬l(fā)現(xiàn)自己在壘城堡的時候并沒有預先考慮到這一點。所以他現(xiàn)在要改造城堡。由于他沒有多余的積木了，他靈機一動，想出了一個巧妙的改造方案。他決定從每一個城堡中挪去一些積木，使得最終每座城堡都一樣高。為了使他的城堡更雄偉，他覺得應該使最后的城堡都盡可能的高。任務：請你幫助小XC編一個程序，根據(jù)他壘的所有城堡的信息，決定應該移去哪些積木才能獲得最佳的效果?！据斎胛募康谝恍惺且粋€整數(shù)N(N=100)，表示一共有幾座城堡。以下N行每行是一系列非負整數(shù)，用一個空格分隔，按從下往上的順序依次給出一座城堡中所有積木的棱長。用1結束。一座城堡中的積木不超過100塊，每塊積木的棱長不超過100。【輸出文件】一個整數(shù)，表示最后城堡的最大可能的高度。如果找不到合適的方案，則輸出0。【輸入樣例】22 1 –13 2 1 1【輸出樣例】3【提交鏈接】【問題分析】首先要說明一點，可以挪走任意一個積木，不見得是最上面的。初看題目有點茫然，但抽象一下就。。其實塔好積木在拿走就相當于當初搭的時候沒選拿走的積木。這樣一轉化思維問題就清楚了。把積木可搭建的最大高度看做背包的載重，每塊積木的高度就是物品的重量。也就是用給定的物品裝指定的包，使每個包裝的物品一樣多，且在符合條件的前提下盡量多。這樣就變成經典的背包問題了。對于每一個城堡求一次，最終找到每一個城堡都可達到的最大高度即可?！驹创a1】constmaxhig=7000。maxn=100。varn,top:longint。opt:array[0..maxn,0..maxhig] of boolean。a:array[0..maxn] of longint。procedure init。vari:longint。beginreadln(n)。fillchar(opt,sizeof(opt),false)。for i:=1 to n doopt[i,0]:=true。end。function can(m:longint):boolean。vari:longint。begincan:=true。for i:=1 to n doif not opt[i,m] thenexit(false)。end。procedure main。varii,m,tothig,i,j,ans:longint。beginfor ii:=1 to n dobegintop:=0。read(m)。tothig:=0。while m0 dobegininc(top)。a[top]:=m。inc(tothig,m)。read(m)。end。for i:=1 to top dofor j:=tothig downto 1 doif (ja[i]=0) and (opt[ii,ja[i]]) thenopt[ii,j]:=true。end。ans:=maxhig。while not opt[1,ans] dodec(ans)。while not can(ans) dodec(ans)。writeln(ans)。end。begininit。main。end.回顧上面的內容充分說明動態(tài)規(guī)劃的本質就是遞推。其實按照我的理解（動規(guī)涉及最優(yōu)決策，遞推是單純的總結）背包問題的簡化版更準確點算是遞推而非動態(tài)規(guī)劃，至于動歸和遞推之間的界線本來就很模糊（至少我這么認為）把它看做什么都可以，沒必要咬文嚼字?；氐?/1背包的原問題上（如果你忘了就去上面看看）。如果在不知道這個模型的情況下我們怎么做這個題呢？這就要用到第一節(jié)提到的方法二：三要素法。題目中明確說明對于一個物品要不就拿走要不就放下，其實題目赤裸裸的告訴我們決策就是不拿（用0表示）或拿（用1表示）。這樣想都不用想就知道了決策，這也是本題的突破口。知道了決策寫個搜索的程序應該是很輕松的了。那么階段是什么呢？顯然，給你一堆東西讓你往包里塞，你當然是一個一個的那來，塞進去。那么階段很明顯就是物品的個數(shù)。狀態(tài)又是什么呢？有的人在裝東西是有個習慣（比如說我）就是先把東西分類，然后把同類的東西打個小包，最后在把小包放進去，我們可以按這個思想給物品打一些小包，也就是按照單位為1的遞增的順序準備好多小包，比如載重是6的包，可以為它準備載重是1，2，3，4，5的小包。這樣狀態(tài)就可以想出來了：設計狀態(tài)opt[i，j]表示裝第i個物品時載重為j的包可以裝到的最大價值。opt[i1,j] (jw[i]0，i0)狀態(tài)轉移方程：opt[i,j]=max{opt[i1,j],opt[i1,jw[i]]+v[i]} (jw[i]=0,i0)(w[i]:第i個物品的重量，v[i]第i個物品的價值)解釋：要載重為j的背包空出w[i]（jw[i]）的空間且裝上第i個物品，比不裝獲得的價值大就裝上它。邊界條件：opt[0,i]=0。 (i∈{1..S})注：這種二維的狀態(tài)表示應該在下節(jié)講，但是為了方便理解先在這里說了。上面的方法動態(tài)規(guī)劃三要素都很明顯，實現(xiàn)也很簡單。但是在我初學背包時卻用另外一種一維的狀態(tài)表示法。用第一節(jié)說的思考方法五（放寬約束和增加約束）在重新思考一下這個問題：怎么放寬約束呢？把題目中的價值去掉，不考慮價值即最優(yōu)就變成背包問題的簡化版了。那簡化版的求解對我們有何啟示呢？再一次增加約束：背包只能裝滿。顯然對于N個裝滿背包的方案中只要找到一個價值最大的就是問題的解。那么裝不滿怎么辦呢？其實裝不滿背包，它總要達到一定的重量（X）。我們可以把這種情況看作是裝滿一個載重為X的小包?？偨Y一下上面的思維過程：放寬約束讓我們找到問題的突破口——和背包問題簡化版一樣，我們可以卻定載重為S的背包是否可以裝滿。增加約束讓我們找到問題的求解方法——在裝滿背包的方案中選擇最優(yōu)的一個方案。這樣問題就解決了。設計一個狀態(tài)opt[j]表示裝滿載重為j的背包可獲得的最大價值。對于第i個物品，只要opt[jw[i]]可以裝滿且opt[jw[i]]+v[i]比opt[j]大就裝上這個物品（更新opt[j]）。怎么使opt[j]既有是否構成又有最優(yōu)的概念呢？opt[j]只表示最優(yōu)，只不過使初始條件+1，判斷opt[j]是否為0，如果opt[j]=0說明j裝不滿。邊界條件：opt[0]=1。狀態(tài)轉移方程：opt[j]=max{opt[jw[i]]} (0in,w[i]=j=S)問題解： ans=max{opt[i]}1 (0i=s)時間復雜度：階段數(shù)O(S)*狀態(tài)數(shù)（O(N)）*轉移代價（O(1)）=O（SN）下面看幾個例題：例題8 采藥 () 來源：NOIP2005（普及組） 第三題【問題描述】辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質，給他出了一個難題。醫(yī)師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大?！比绻闶浅匠?，你能完成這個任務嗎？【輸入文件】（1 = T = 1000）和M（1 = M = 100）