//------------------------------------------------------------

對于環(huán)形的動態(tài)規(guī)劃，

可以把數(shù)組下標復制一份然后進行動態(tài)規(guī)劃

//------------------------------------------------------------

在動態(tài)規(guī)劃的具體編程中，可能許多時候?qū)懗隽苏_的狀態(tài)轉(zhuǎn)移方程，但編寫后的程序卻得不到正確解，這很有可能是因為動態(tài)規(guī)劃的循環(huán)的順逆序，或者循環(huán)的內(nèi)外層出現(xiàn)了錯誤。

在這里忽略其他資料中的理論知識，而具體說動態(tài)規(guī)劃是如何實現(xiàn)的。

// 在這里的給出的全部代碼都沒有經(jīng)過調(diào)試而直接寫出

// 如果出現(xiàn)錯誤，請指出

從01背包開始說起。

稍微掌握動態(tài)規(guī)劃的人都可以熟練地寫出如下代碼：

for(i=1;i<=n;i++)
  for(j=v;j>=c[i];j--)
    d[j]=max(d[j],d[j-c[i]]+w[i])；

一般的動態(tài)規(guī)劃都是先枚舉狀態(tài)再枚舉決策，可能初學者不明白以上的代碼是怎么回事，因為這是降維之后的狀態(tài)表示，降維之前的是：

d[i][j]=max(d[i-1][j],d[i-1][j-c[i]]+w[i])；

之所以可以降維是因為：觀察狀態(tài)轉(zhuǎn)移方程，第i次的決策只與第i-1次所記錄的狀態(tài)有關，于是想，能不能有一種方法只用一維數(shù)組，就可以在狀態(tài)轉(zhuǎn)移能夠正確進行？答案是肯定的，那就是第二層使用逆序循環(huán)。

NOIp 2006 金明的預算方案

先處理一下給出的物品，分成若干組，轉(zhuǎn)化為分組背包問題。

寫出分組背包的狀態(tài)轉(zhuǎn)移方程：

d[k][j]=max(d[k-1][j],d[k-1][j-c[k][i]]+w[k][i])；

對于分組背包，給出如下代碼：

for 所有組k
  for j=V to 0
    for 所有物品i屬于組k
      d[j]=max(d[j],d[j-c[k][i]]+w[k][i])；

// 《背包問題九講》中的代碼似乎有點錯誤

同樣，先觀察狀態(tài)轉(zhuǎn)移方程，還是只取決于第k-1組記錄的狀態(tài)，又要使每組中物品只選一件或者一件都不選。這樣就確定了分組背包只能是上面的循環(huán)次序，因為只有這樣在第k組決策的時候才能保證從第k-1組的狀態(tài)轉(zhuǎn)移而來；簡單地說就是，在第二層固定了前k組物品占用的空間，那么無論選擇哪一個i，最終這個狀態(tài)都只能被第k組的一個物品占用；試想如果像《背包問題九講》中那樣把第二層循環(huán)和第三層循環(huán)顛倒過來，那么就有可能第k層的狀態(tài)由第k層的狀態(tài)轉(zhuǎn)移而來，從而不能保證最多選擇一件物品。

Vijos GF

二維費用的背包。

狀態(tài)轉(zhuǎn)移方程直接給出如下：

d[i][j][k]=max(d[i-1][j][k],d[i-1][j-c1[i]][k-c2[i]]+w[i])；

同樣可以降到二維，因為是每個GF只能選擇一次（題目中好像沒有這么說，很久之前做的了，不太記得了，但是現(xiàn)實生活中的經(jīng)驗告訴我們每個GF只能選擇一次），所以在循環(huán)枚舉j和k的時候要使用逆序。

Vijos 情敵

當然可以理解為和“金明的預算方案”一樣，是有依賴關系的背包問題，但是這道題卻在數(shù)據(jù)的規(guī)模上告訴我們用那種方法是不可行的。更好的做法是搜索和動態(tài)規(guī)劃結(jié)合，每次枚舉超級情敵在第一個月消滅、第二個月消滅、第三個月消滅（即不消滅），然后對其余情敵進行動態(tài)規(guī)劃。

省略搜索部分，而著重說說動態(tài)規(guī)劃。

狀態(tài)轉(zhuǎn)移方程：

d[i][j][k]=max(d[i-1][j][k],d[i-1][j-c1[i]][k],d[i-1][j][k-c2[i]])；

由于有可能某個超級情敵沒有被消滅，而在枚舉i的時候枚舉了這個超級情敵，如果在這時直接判斷后continue，可能造成d[i]層的空缺，以至于d[i+1]層的錯誤。所以在處理這樣可能出現(xiàn)某一層出現(xiàn)空缺的情況時，要把空缺的那一層全部從它的上一層把狀態(tài)繼承下來，以保證后來的狀態(tài)轉(zhuǎn)移的正確。

總結(jié)一下。

對于一道題目寫出狀態(tài)轉(zhuǎn)移方程之后，程序的實現(xiàn)有時候是顯而易見的，但有時候卻又需要思考一番。這時候還是需要立足于狀態(tài)轉(zhuǎn)移方程，另外還要考慮到題目中的一些限制條件，設計合適的循環(huán)順逆序和內(nèi)外層。

//------------------------------------------------------------