如果機(jī)房馬上要關(guān)門(mén)了，或者你急著要和MM約會(huì)，請(qǐng)直接跳到第六個(gè)自然段。
我們這里說(shuō)的KMP不是拿來(lái)放電影的（雖然我很喜歡這個(gè)軟件），而是一種算法。KMP算法是拿來(lái)處理字符串匹配的。換句話說(shuō)，給你兩個(gè)字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。比如，字符串A="I'm matrix67"，字符串B="matrix"，我們就說(shuō)B是A的子串。你可以委婉地問(wèn)你的MM：“假如你要向你喜歡的人表白的話，我的名字是你的告白語(yǔ)中的子串嗎？”
解決這類(lèi)問(wèn)題，通常我們的方法是枚舉從A串的什么位置起開(kāi)始與B匹配，然后驗(yàn)證是否匹配。假如A串長(zhǎng)度為n，B串長(zhǎng)度為m，那么這種方法的復(fù)雜度是O (mn)的。雖然很多時(shí)候復(fù)雜度達(dá)不到mn（驗(yàn)證時(shí)只看頭一兩個(gè)字母就發(fā)現(xiàn)不匹配了），但我們有許多“最壞情況”，比如，A= "aaaaaaaaaaaaaaaaaaaaaaaaaab"，B="aaaaaaaab"。我們將介紹的是一種最壞情況下O(n)的算法（這里假設(shè) m<=n），即傳說(shuō)中的KMP算法。
之所以叫做KMP，是因?yàn)檫@個(gè)算法是由Knuth、Morris、Pratt三個(gè)提出來(lái)的，取了這三個(gè)人的名字的頭一個(gè)字母。這時(shí)，或許你突然明白了AVL 樹(shù)為什么叫AVL，或者Bellman-Ford為什么中間是一杠不是一個(gè)點(diǎn)。有時(shí)一個(gè)東西有七八個(gè)人研究過(guò)，那怎么命名呢？通常這個(gè)東西干脆就不用人名字命名了，免得發(fā)生爭(zhēng)議，比如“3x+1問(wèn)題”。扯遠(yuǎn)了。
個(gè)人認(rèn)為KMP是最沒(méi)有必要講的東西，因?yàn)檫@個(gè)東西網(wǎng)上能找到很多資料。但網(wǎng)上的講法基本上都涉及到“移動(dòng)(shift)”、“Next函數(shù)”等概念，這非常容易產(chǎn)生誤解（至少一年半前我看這些資料學(xué)習(xí)KMP時(shí)就沒(méi)搞清楚）。在這里，我換一種方法來(lái)解釋KMP算法。
假如，A="abababaababacb"，B="ababacb"，我們來(lái)看看KMP是怎么工作的。我們用兩個(gè)指針i和j分別表示，A[i-j+ 1..i]與B[1..j]完全相等。也就是說(shuō)，i是不斷增加的，隨著i的增加j相應(yīng)地變化，且j滿足以A[i]結(jié)尾的長(zhǎng)度為j的字符串正好匹配B串的前 j個(gè)字符（j當(dāng)然越大越好），現(xiàn)在需要檢驗(yàn)A[i+1]和B[j+1]的關(guān)系。當(dāng)A[i+1]=B[j+1]時(shí)，i和j各加一；什么時(shí)候j=m了，我們就說(shuō)B是A的子串（B串已經(jīng)整完了），并且可以根據(jù)這時(shí)的i值算出匹配的位置。當(dāng)A[i+1]<>B[j+1]，KMP的策略是調(diào)整j的位置（減小j值）使得A[i-j+1..i]與B[1..j]保持匹配且新的B[j+1]恰好與A[i+1]匹配（從而使得i和j能繼續(xù)增加）。我們看一看當(dāng) i=j=5時(shí)的情況。
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7 此時(shí)，A[6]<>B[6]。這表明，此時(shí)j不能等于5了，我們要把j改成比它小的值j'。j'可能是多少呢？仔細(xì)想一下，我們發(fā)現(xiàn)，j'必須要使得B[1..j]中的頭j'個(gè)字母和末j'個(gè)字母完全相等（這樣j變成了j'后才能繼續(xù)保持i和j的性質(zhì)）。這個(gè)j'當(dāng)然要越大越好。在這里，B [1..5]="ababa"，頭3個(gè)字母和末3個(gè)字母都是"aba"。而當(dāng)新的j為3時(shí)，A[6]恰好和B[4]相等。于是，i變成了6，而j則變成了 4：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7 從上面的這個(gè)例子，我們可以看到，新的j可以取多少與i無(wú)關(guān)，只與B串有關(guān)。我們完全可以預(yù)處理出這樣一個(gè)數(shù)組P[j]，表示當(dāng)匹配到B數(shù)組的第j個(gè)字母而第j+1個(gè)字母不能匹配了時(shí)，新的j最大是多少。P[j]應(yīng)該是所有滿足B[1..P[j]]=B[j-P[j]+1..j]的最大值。
再后來(lái)，A[7]=B[5]，i和j又各增加1。這時(shí)，又出現(xiàn)了A[i+1]<>B[j+1]的情況：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7 由于P[5]=3，因此新的j=3：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7 這時(shí)，新的j=3仍然不能滿足A[i+1]=B[j+1]，此時(shí)我們?cè)俅螠p小j值，將j再次更新為P[3]：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7 現(xiàn)在，i還是7，j已經(jīng)變成1了。而此時(shí)A[8]居然仍然不等于B[j+1]。這樣，j必須減小到P[1]，即0：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 0 1 2 3 4 5 6 7 終于，A[8]=B[1]，i變?yōu)?，j為1。事實(shí)上，有可能j到了0仍然不能滿足A[i+1]=B[j+1]（比如A[8]="d"時(shí)）。因此，準(zhǔn)確的說(shuō)法是，當(dāng)j=0了時(shí)，我們?cè)黾觟值但忽略j直到出現(xiàn)A[i]=B[1]為止。
這個(gè)過(guò)程的代碼很短（真的很短），我們?cè)谶@里給出：
j:=0;
for i:=1 to n do
begin
while (j>0) and (B[j+1]<>A[i]) do j:=P[j];
if B[j+1]=A[i] then j:=j+1;
if j=m then
begin
writeln('Pattern occurs with shift ',i-m);
j:=P[j];
end;
end; 最后的j:=P[j]是為了讓程序繼續(xù)做下去，因?yàn)槲覀冇锌赡苷业蕉嗵幤ヅ洹?br> 這個(gè)程序或許比想像中的要簡(jiǎn)單，因?yàn)閷?duì)于i值的不斷增加，代碼用的是for循環(huán)。因此，這個(gè)代碼可以這樣形象地理解：掃描字符串A，并更新可以匹配到B的什么位置。
現(xiàn)在，我們還遺留了兩個(gè)重要的問(wèn)題：一，為什么這個(gè)程序是線性的；二，如何快速預(yù)處理P數(shù)組。
為什么這個(gè)程序是O(n)的？其實(shí)，主要的爭(zhēng)議在于，while循環(huán)使得執(zhí)行次數(shù)出現(xiàn)了不確定因素。我們將用到時(shí)間復(fù)雜度的攤還分析中的主要策略，簡(jiǎn)單地說(shuō)就是通過(guò)觀察某一個(gè)變量或函數(shù)值的變化來(lái)對(duì)零散的、雜亂的、不規(guī)則的執(zhí)行次數(shù)進(jìn)行累計(jì)。KMP的時(shí)間復(fù)雜度分析可謂攤還分析的典型。我們從上述程序的j 值入手。每一次執(zhí)行while循環(huán)都會(huì)使j減小（但不能減成負(fù)的），而另外的改變j值的地方只有第五行。每次執(zhí)行了這一行，j都只能加1；因此，整個(gè)過(guò)程中j最多加了n個(gè)1。于是，j最多只有n次減小的機(jī)會(huì)（j值減小的次數(shù)當(dāng)然不能超過(guò)n，因?yàn)閖永遠(yuǎn)是非負(fù)整數(shù)）。這告訴我們，while循環(huán)總共最多執(zhí)行了n次。按照攤還分析的說(shuō)法，平攤到每次for循環(huán)中后，一次for循環(huán)的復(fù)雜度為O(1)。整個(gè)過(guò)程顯然是O(n)的。這樣的分析對(duì)于后面P數(shù)組預(yù)處理的過(guò)程同樣有效，同樣可以得到預(yù)處理過(guò)程的復(fù)雜度為O(m)。
預(yù)處理不需要按照P的定義寫(xiě)成O(m^2)甚至O(m^3)的。我們可以通過(guò)P[1],P[2],...,P[j-1]的值來(lái)獲得P[j]的值。對(duì)于剛才的B="ababacb"，假如我們已經(jīng)求出了P[1],P[2],P[3]和P[4]，看看我們應(yīng)該怎么求出P[5]和P[6]。P[4]=2，那么P [5]顯然等于P[4]+1，因?yàn)橛蒔[4]可以知道，B[1,2]已經(jīng)和B[3,4]相等了，現(xiàn)在又有B[3]=B[5]，所以P[5]可以由P[4] 后面加一個(gè)字符得到。P[6]也等于P[5]+1嗎？顯然不是，因?yàn)锽[ P[5]+1 ]<>B[6]。那么，我們要考慮“退一步”了。我們考慮P[6]是否有可能由P[5]的情況所包含的子串得到，即是否P[6]=P[ P[5] ]+1。這里想不通的話可以仔細(xì)看一下：
1 2 3 4 5 6 7
B = a b a b a c b
P = 0 0 1 2 3 ? P[5]=3是因?yàn)锽[1..3]和B[3..5]都是"aba"；而P[3]=1則告訴我們，B[1]、B[3]和B[5]都是"a"。既然P[6]不能由P[5]得到，或許可以由P[3]得到（如果B[2]恰好和B[6]相等的話，P[6]就等于P[3]+1了）。顯然，P[6]也不能通過(guò)P[3]得到，因?yàn)锽[2]<>B[6]。事實(shí)上，這樣一直推到P[1]也不行，最后，我們得到，P[6]=0。
怎么這個(gè)預(yù)處理過(guò)程跟前面的KMP主程序這么像呢？其實(shí)，KMP的預(yù)處理本身就是一個(gè)B串“自我匹配”的過(guò)程。它的代碼和上面的代碼神似：
P[1]:=0;
j:=0;
for i:=2 to m do
begin
while (j>0) and (B[j+1]<>B[i]) do j:=P[j];
if B[j+1]=B[i] then j:=j+1;
P[i]:=j;
end; 最后補(bǔ)充一點(diǎn)：由于KMP算法只預(yù)處理B串，因此這種算法很適合這樣的問(wèn)題：給定一個(gè)B串和一群不同的A串，問(wèn)B是哪些A串的子串。
串匹配是一個(gè)很有研究?jī)r(jià)值的問(wèn)題。事實(shí)上，我們還有后綴樹(shù)，自動(dòng)機(jī)等很多方法，這些算法都巧妙地運(yùn)用了預(yù)處理，從而可以在線性的時(shí)間里解決字符串的匹配。我們以后來(lái)說(shuō)。
昨天發(fā)現(xiàn)一個(gè)特別暈的事，知道怎么去掉BitComet的廣告嗎？把界面語(yǔ)言設(shè)成英文就行了。
還有，金山詞霸和Dr.eye都可以去自殺了，Babylon素王道。
來(lái)自：
http://www.matrix67.com/blog/archives/115
P01: 01背包問(wèn)題
題目
有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。
基本思路
這是最基礎(chǔ)的背包問(wèn)題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。
用子問(wèn)題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。
這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問(wèn)題的方程都是由它衍生出來(lái)的。所以有必要將它詳細(xì)解釋一下：“將前i件物品放入容量為v的背包中”這個(gè)子問(wèn)題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問(wèn)題。如果不放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”；如果放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時(shí)能獲得的最大價(jià)值就是f [i-1][v-c[i]]再加上通過(guò)放入第i件物品獲得的價(jià)值w[i]。
注意f[i][v]有意義當(dāng)且僅當(dāng)存在一個(gè)前i件物品的子集，其費(fèi)用總和為v。所以按照這個(gè)方程遞推完畢后，最終的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。如果將狀態(tài)的定義中的“恰”字去掉，在轉(zhuǎn)移方程中就要再加入一項(xiàng)f[i][v-1]，這樣就可以保證f[N] [V]就是最后的答案。至于為什么這樣就可以，由你自己來(lái)體會(huì)了。
優(yōu)化空間復(fù)雜度
以上方法的時(shí)間和空間復(fù)雜度均為O(N*V)，其中時(shí)間復(fù)雜度基本已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以優(yōu)化到O(V)。
先考慮上面講的基本思路如何實(shí)現(xiàn)，肯定是有一個(gè)主循環(huán)i=1..N，每次算出來(lái)二維數(shù)組f[i][0..V]的所有值。那么，如果只用一個(gè)數(shù)組f [0..V]，能不能保證第i次循環(huán)結(jié)束后f[v]中表示的就是我們定義的狀態(tài)f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]兩個(gè)子問(wèn)題遞推而來(lái)，能否保證在推f[i][v]時(shí)（也即在第i次主循環(huán)中推f[v]時(shí)）能夠得到f[i-1][v]和f[i-1][v -c[i]]的值呢？事實(shí)上，這要求在每次主循環(huán)中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時(shí)f[v-c[i]]保存的是狀態(tài)f[i -1][v-c[i]]的值。偽代碼如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當(dāng)于我們的轉(zhuǎn)移方程f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]}，因?yàn)楝F(xiàn)在的f[v-c[i]]就相當(dāng)于原來(lái)的f[i-1][v-c[i]]。如果將v的循環(huán)順序從上面的逆序改成順序的話，那么則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另一個(gè)重要的背包問(wèn)題P02最簡(jiǎn)捷的解決方案，故學(xué)習(xí)只用一維數(shù)組解01背包問(wèn)題是十分必要的。
總結(jié)
01背包問(wèn)題是最基本的背包問(wèn)題，它包含了背包問(wèn)題中設(shè)計(jì)狀態(tài)、方程的最基本思想，另外，別的類(lèi)型的背包問(wèn)題往往也可以轉(zhuǎn)換成01背包問(wèn)題求解。故一定要仔細(xì)體會(huì)上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及最后怎樣優(yōu)化的空間復(fù)雜度。
P02: 完全背包問(wèn)題
題目
有N種物品和一個(gè)容量為V的背包，每種物品都有無(wú)限件可用。第i種物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。
基本思路
這個(gè)問(wèn)題非常類(lèi)似于01背包問(wèn)題，所不同的是每種物品有無(wú)限件。也就是從每種物品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01背包時(shí)的思路，令f[i][v]表示前i種物品恰放入一個(gè)容量為v的背包的最大權(quán)值。仍然可以按照每種物品不同的策略寫(xiě)出狀態(tài)轉(zhuǎn)移方程，像這樣：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<= v}。這跟01背包問(wèn)題一樣有O(N*V)個(gè)狀態(tài)需要求解，但求解每個(gè)狀態(tài)的時(shí)間則不是常數(shù)了，求解狀態(tài)f[i][v]的時(shí)間是O(v/c[i])，總的復(fù)雜度是超過(guò)O(VN)的。
將01背包問(wèn)題的基本思路加以改進(jìn)，得到了這樣一個(gè)清晰的方法。這說(shuō)明01背包問(wèn)題的方程的確是很重要，可以推及其它類(lèi)型的背包問(wèn)題。但我們還是試圖改進(jìn)這個(gè)復(fù)雜度。
一個(gè)簡(jiǎn)單有效的優(yōu)化
完全背包問(wèn)題有一個(gè)很簡(jiǎn)單有效的優(yōu)化，是這樣的：若兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j]，則將物品j去掉，不用考慮。這個(gè)優(yōu)化的正確性顯然：任何情況下都可將價(jià)值小費(fèi)用高得j換成物美價(jià)廉的i，得到至少不會(huì)更差的方案。對(duì)于隨機(jī)生成的數(shù)據(jù)，這個(gè)方法往往會(huì)大大減少物品的件數(shù)，從而加快速度。然而這個(gè)并不能改善最壞情況的復(fù)雜度，因?yàn)橛锌赡芴貏e設(shè)計(jì)的數(shù)據(jù)可以一件物品也去不掉。
轉(zhuǎn)化為01背包問(wèn)題求解
既然01背包問(wèn)題是最基本的背包問(wèn)題，那么我們可以考慮把完全背包問(wèn)題轉(zhuǎn)化為01背包問(wèn)題來(lái)解。最簡(jiǎn)單的想法是，考慮到第i種物品最多選V/c [i]件，于是可以把第i種物品轉(zhuǎn)化為V/c[i]件費(fèi)用及價(jià)值均不變的物品，然后求解這個(gè)01背包問(wèn)題。這樣完全沒(méi)有改進(jìn)基本思路的時(shí)間復(fù)雜度，但這畢竟給了我們將完全背包問(wèn)題轉(zhuǎn)化為01背包問(wèn)題的思路：將一種物品拆成多件物品。
更高效的轉(zhuǎn)化方法是：把第i種物品拆成費(fèi)用為c[i]*2^k、價(jià)值為w[i]*2^k的若干件物品，其中k滿足c[i]*2^k<V。這是二進(jìn)制的思想，因?yàn)椴还茏顑?yōu)策略選幾件第i種物品，總可以表示成若干個(gè)2^k件物品的和。這樣把每種物品拆成O(log(V/c[i]))件物品，是一個(gè)很大的改進(jìn)。 但我們有更優(yōu)的O(VN)的算法。 * O(VN)的算法 這個(gè)算法使用一維數(shù)組，先看偽代碼： <pre class"example"> for i=1..N for v=0..V f[v]=max{f[v],f[v-c[i]]+w[i]};
你會(huì)發(fā)現(xiàn)，這個(gè)偽代碼與P01的偽代碼只有v的循環(huán)次序不同而已。為什么這樣一改就可行呢？首先想想為什么P01中要按照v=V..0的逆序來(lái)循環(huán)。這是因?yàn)橐ＷC第i次循環(huán)中的狀態(tài)f[i][v]是由狀態(tài)f[i-1][v-c[i]]遞推而來(lái)。換句話說(shuō)，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時(shí)，依據(jù)的是一個(gè)絕無(wú)已經(jīng)選入第i件物品的子結(jié)果f[i-1][v-c[i]]。而現(xiàn)在完全背包的特點(diǎn)恰是每種物品可選無(wú)限件，所以在考慮“加選一件第i種物品”這種策略時(shí)，卻正需要一個(gè)可能已選入第i種物品的子結(jié)果f[i][v-c[i]]，所以就可以并且必須采用v= 0..V的順序循環(huán)。這就是這個(gè)簡(jiǎn)單的程序?yàn)楹纬闪⒌牡览怼?
這個(gè)算法也可以以另外的思路得出。例如，基本思路中的狀態(tài)轉(zhuǎn)移方程可以等價(jià)地變形成這種形式：f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}，將這個(gè)方程用一維數(shù)組實(shí)現(xiàn)，便得到了上面的偽代碼。
總結(jié)
完全背包問(wèn)題也是一個(gè)相當(dāng)基礎(chǔ)的背包問(wèn)題，它有兩個(gè)狀態(tài)轉(zhuǎn)移方程，分別在“基本思路”以及“O(VN)的算法“的小節(jié)中給出。希望你能夠?qū)@兩個(gè)狀態(tài)轉(zhuǎn)移方程都仔細(xì)地體會(huì)，不僅記住，也要弄明白它們是怎么得出來(lái)的，最好能夠自己想一種得到這些方程的方法。事實(shí)上，對(duì)每一道動(dòng)態(tài)規(guī)劃題目都思考其方程的意義以及如何得來(lái)，是加深對(duì)動(dòng)態(tài)規(guī)劃的理解、提高動(dòng)態(tài)規(guī)劃功力的好方法。
P03: 多重背包問(wèn)題
題目
有N種物品和一個(gè)容量為V的背包。第i種物品最多有n[i]件可用，每件費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。
基本算法
這題目和完全背包問(wèn)題很類(lèi)似。基本的方程只需將完全背包問(wèn)題的方程略微一改即可，因?yàn)閷?duì)于第i種物品有n[i]+1種策略：取0件，取1件……取 n[i]件。令f[i][v]表示前i種物品恰放入一個(gè)容量為v的背包的最大權(quán)值，則：f[i][v]=max{f[i-1][v-k*c[i]]+ k*w[i]|0<=k<=n[i]}。復(fù)雜度是O(V*∑n[i])。
轉(zhuǎn)化為01背包問(wèn)題
另一種好想好寫(xiě)的基本方法是轉(zhuǎn)化為01背包求解：把第i種物品換成n[i]件01背包中的物品，則得到了物品數(shù)為∑n[i]的01背包問(wèn)題，直接求解，復(fù)雜度仍然是O(V*∑n[i])。
但是我們期望將它轉(zhuǎn)化為01背包問(wèn)題之后能夠像完全背包一樣降低復(fù)雜度。仍然考慮二進(jìn)制的思想，我們考慮把第i種物品換成若干件物品，使得原問(wèn)題中第i種物品可取的每種策略——取0..n[i]件——均能等價(jià)于取若干件代換以后的物品。另外，取超過(guò)n[i]件的策略必不能出現(xiàn)。
方法是：將第i種物品分成若干件物品，其中每件物品有一個(gè)系數(shù)，這件物品的費(fèi)用和價(jià)值均是原來(lái)的費(fèi)用和價(jià)值乘以這個(gè)系數(shù)。使這些系數(shù)分別為 1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數(shù)。例如，如果n[i]為13，就將這種物品分成系數(shù)分別為1,2,4,6的四件物品。
分成的這幾件物品的系數(shù)和為n[i]，表明不可能取多于n[i]件的第i種物品。另外這種方法也能保證對(duì)于0..n[i]間的每一個(gè)整數(shù)，均可以用若干個(gè)系數(shù)的和表示，這個(gè)證明可以分0..2^k-1和2^k..n[i]兩段來(lái)分別討論得出，并不難，希望你自己思考嘗試一下。
這樣就將第i種物品分成了O(log n[i])種物品，將原問(wèn)題轉(zhuǎn)化為了復(fù)雜度為O(V*∑log n[i])的01背包問(wèn)題，是很大的改進(jìn)。
O(VN)的算法
多重背包問(wèn)題同樣有O(VN)的算法。這個(gè)算法基于基本算法的狀態(tài)轉(zhuǎn)移方程，但應(yīng)用單調(diào)隊(duì)列的方法使每個(gè)狀態(tài)的值可以以均攤O(1)的時(shí)間求解。由于用單調(diào)隊(duì)列優(yōu)化的DP已超出了NOIP的范圍，故本文不再展開(kāi)講解。我最初了解到這個(gè)方法是在樓天成的“男人八題”幻燈片上。
小結(jié)
這里我們看到了將一個(gè)算法的復(fù)雜度由O(V*∑n[i])改進(jìn)到O(V*∑log n[i])的過(guò)程，還知道了存在應(yīng)用超出NOIP范圍的知識(shí)的O(VN)算法。希望你特別注意“拆分物品”的思想和方法，自己證明一下它的正確性，并用盡量簡(jiǎn)潔的程序來(lái)實(shí)現(xiàn)。
P04: 混合三種背包問(wèn)題
問(wèn)題
如果將P01、P02、P03混合起來(lái)。也就是說(shuō)，有的物品只可以取一次（01背包），有的物品可以取無(wú)限次（完全背包），有的物品可以取的次數(shù)有一個(gè)上限（多重背包）。應(yīng)該怎么求解呢？
01背包與完全背包的混合
考慮到在P01和P02中最后給出的偽代碼只有一處不同，故如果只有兩類(lèi)物品：一類(lèi)物品只能取一次，另一類(lèi)物品可以取無(wú)限次，那么只需在對(duì)每個(gè)物品應(yīng)用轉(zhuǎn)移方程時(shí)，根據(jù)物品的類(lèi)別選用順序或逆序的循環(huán)即可，復(fù)雜度是O(VN)。偽代碼如下：
for i=1..N
if 第i件物品是01背包
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
else if 第i件物品是完全背包
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]};
再加上多重背包
如果再加上有的物品最多可以取有限次，那么原則上也可以給出O(VN)的解法：遇到多重背包類(lèi)型的物品用單調(diào)隊(duì)列解即可。但如果不考慮超過(guò)NOIP范圍的算法的話，用P03中將每個(gè)這類(lèi)物品分成O(log n[i])個(gè)01背包的物品的方法也已經(jīng)很優(yōu)了。
小結(jié)
有人說(shuō)，困難的題目都是由簡(jiǎn)單的題目疊加而來(lái)的。這句話是否公理暫且存之不論，但它在本講中已經(jīng)得到了充分的體現(xiàn)。本來(lái)01背包、完全背包、多重背包都不是什么難題，但將它們簡(jiǎn)單地組合起來(lái)以后就得到了這樣一道一定能?chē)樀共簧偃说念}目。但只要基礎(chǔ)扎實(shí)，領(lǐng)會(huì)三種基本背包問(wèn)題的思想，就可以做到把困難的題目拆分成簡(jiǎn)單的題目來(lái)解決。
P05: 二維費(fèi)用的背包問(wèn)題
問(wèn)題
二維費(fèi)用的背包問(wèn)題是指：對(duì)于每件物品，具有兩種不同的費(fèi)用；選擇這件物品必須同時(shí)付出這兩種代價(jià)；對(duì)于每種代價(jià)都有一個(gè)可付出的最大值（背包容量）。問(wèn)怎樣選擇物品可以得到最大的價(jià)值。設(shè)這兩種代價(jià)分別為代價(jià)1和代價(jià)2，第i件物品所需的兩種代價(jià)分別為a[i]和b[i]。兩種代價(jià)可付出的最大值（兩種背包容量）分別為V和U。物品的價(jià)值為w[i]。
算法
費(fèi)用加了一維，只需狀態(tài)也加一維即可。設(shè)f[i][v][u]表示前i件物品付出兩種代價(jià)分別為v和u時(shí)可獲得的最大價(jià)值。狀態(tài)轉(zhuǎn)移方程就是：f [i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}。如前述方法，可以只使用二維的數(shù)組：當(dāng)每件物品只可以取一次時(shí)變量v和u采用順序的循環(huán)，當(dāng)物品有如完全背包問(wèn)題時(shí)采用逆序的循環(huán)。當(dāng)物品有如多重背包問(wèn)題時(shí)拆分物品。
物品總個(gè)數(shù)的限制
有時(shí)，“二維費(fèi)用”的條件是以這樣一種隱含的方式給出的：最多只能取M件物品。這事實(shí)上相當(dāng)于每件物品多了一種“件數(shù)”的費(fèi)用，每個(gè)物品的件數(shù)費(fèi)用均為1，可以付出的最大件數(shù)費(fèi)用為M。換句話說(shuō)，設(shè)f[v][m]表示付出費(fèi)用v、最多選m件時(shí)可得到的最大價(jià)值，則根據(jù)物品的類(lèi)型（01、完全、多重）用不同的方法循環(huán)更新，最后在f[0..V][0..M]范圍內(nèi)尋找答案。
另外，如果要求“恰取M件物品”，則在f[0..V][M]范圍內(nèi)尋找答案。
小結(jié)
事實(shí)上，當(dāng)發(fā)現(xiàn)由熟悉的動(dòng)態(tài)規(guī)劃題目變形得來(lái)的題目時(shí)，在原來(lái)的狀態(tài)中加一緯以滿足新的限制是一種比較通用的方法。希望你能從本講中初步體會(huì)到這種方法。
P06: 分組的背包問(wèn)題
問(wèn)題
有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。
算法
這個(gè)問(wèn)題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說(shuō)設(shè)f[k][v]表示前k組物品花費(fèi)費(fèi)用v能取得的最大權(quán)值，則有f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i屬于第k組}。
使用一維數(shù)組的偽代碼如下：
for 所有的組k
for 所有的i屬于組k
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]} 我覺(jué)得這個(gè)地方寫(xiě)得有誤 應(yīng)該是：for 所有的組k
for v=V..0
for 所有的i屬于組k
f[v]=max{f[v],f[v-c[i]]+w[i]} by abilitytao 例題見(jiàn)浙大3264
另外，顯然可以對(duì)每組中的物品應(yīng)用P02中“一個(gè)簡(jiǎn)單有效的優(yōu)化”。
小結(jié)
分組的背包問(wèn)題將彼此互斥的若干物品稱(chēng)為一個(gè)組，這建立了一個(gè)很好的模型。不少背包問(wèn)題的變形都可以轉(zhuǎn)化為分組的背包問(wèn)題（例如P07），由分組的背包問(wèn)題進(jìn)一步可定義“泛化物品”的概念，十分有利于解題。
P07: 有依賴的背包問(wèn)題
簡(jiǎn)化的問(wèn)題
這種背包問(wèn)題的物品間存在某種“依賴”的關(guān)系。也就是說(shuō)，i依賴于j，表示若選物品i，則必須選物品j。為了簡(jiǎn)化起見(jiàn)，我們先設(shè)沒(méi)有某個(gè)物品既依賴于別的物品，又被別的物品所依賴；另外，沒(méi)有某件物品同時(shí)依賴多件物品。
算法
這個(gè)問(wèn)題由NOIP2006金明的預(yù)算方案一題擴(kuò)展而來(lái)。遵從該題的提法，將不依賴于別的物品的物品稱(chēng)為“主件”，依賴于某主件的物品稱(chēng)為“附件”。由這個(gè)問(wèn)題的簡(jiǎn)化條件可知所有的物品由若干主件和依賴于每個(gè)主件的一個(gè)附件集合組成。
按照背包問(wèn)題的一般思路，僅考慮一個(gè)主件和它的附件集合。可是，可用的策略非常多，包括：一個(gè)也不選，僅選擇主件，選擇主件后再選擇一個(gè)附件，選擇主件后再選擇兩個(gè)附件……無(wú)法用狀態(tài)轉(zhuǎn)移方程來(lái)表示如此多的策略。（事實(shí)上，設(shè)有n個(gè)附件，則策略有2^n+1個(gè)，為指數(shù)級(jí)。）
考慮到所有這些策略都是互斥的（也就是說(shuō)，你只能選擇一種策略），所以一個(gè)主件和它的附件集合實(shí)際上對(duì)應(yīng)于P06中的一個(gè)物品組，每個(gè)選擇了主件又選擇了若干個(gè)附件的策略對(duì)應(yīng)于這個(gè)物品組中的一個(gè)物品，其費(fèi)用和價(jià)值都是這個(gè)策略中的物品的值的和。但僅僅是這一步轉(zhuǎn)化并不能給出一個(gè)好的算法，因?yàn)槲锲方M中的物品還是像原問(wèn)題的策略一樣多。
再考慮P06中的一句話： 可以對(duì)每組中的物品應(yīng)用P02中“一個(gè)簡(jiǎn)單有效的優(yōu)化”。這提示我們，對(duì)于一個(gè)物品組中的物品，所有費(fèi)用相同的物品只留一個(gè)價(jià)值最大的，不影響結(jié)果。所以，我們可以對(duì)主件i的“附件集合”先進(jìn)行一次01背包，得到費(fèi)用依次為0..V-c[i]所有這些值時(shí)相應(yīng)的最大價(jià)值f'[0..V-c[i]]。那么這個(gè)主件及它的附件集合相當(dāng)于V-c[i]+1個(gè)物品的物品組，其中費(fèi)用為c[i]+k的物品的價(jià)值為f'[k]+w[i]。也就是說(shuō)原來(lái)指數(shù)級(jí)的策略中有很多策略都是冗余的，通過(guò)一次01背包后，將主件i轉(zhuǎn)化為 V-c[i]+1個(gè)物品的物品組，就可以直接應(yīng)用P06的算法解決問(wèn)題了。
更一般的問(wèn)題
更一般的問(wèn)題是：依賴關(guān)系以圖論中“森林”的形式給出（森林即多叉樹(shù)的集合），也就是說(shuō)，主件的附件仍然可以具有自己的附件集合，限制只是每個(gè)物品最多只依賴于一個(gè)物品（只有一個(gè)主件）且不出現(xiàn)循環(huán)依賴。
解決這個(gè)問(wèn)題仍然可以用將每個(gè)主件及其附件集合轉(zhuǎn)化為物品組的方式。唯一不同的是，由于附件可能還有附件，就不能將每個(gè)附件都看作一個(gè)一般的01 背包中的物品了。若這個(gè)附件也有附件集合，則它必定要被先轉(zhuǎn)化為物品組，然后用分組的背包問(wèn)題解出主件及其附件集合所對(duì)應(yīng)的附件組中各個(gè)費(fèi)用的附件所對(duì)應(yīng)的價(jià)值。
事實(shí)上，這是一種樹(shù)形DP，其特點(diǎn)是每個(gè)父節(jié)點(diǎn)都需要對(duì)它的各個(gè)兒子的屬性進(jìn)行一次DP以求得自己的相關(guān)屬性。這已經(jīng)觸及到了“泛化物品”的思想。看完P(guān)08后，你會(huì)發(fā)現(xiàn)這個(gè)“依賴關(guān)系樹(shù)”每一個(gè)子樹(shù)都等價(jià)于一件泛化物品，求某節(jié)點(diǎn)為根的子樹(shù)對(duì)應(yīng)的泛化物品相當(dāng)于求其所有兒子的對(duì)應(yīng)的泛化物品之和。
小結(jié)
NOIP2006的那道背包問(wèn)題我做得很失敗，寫(xiě)了上百行的代碼，卻一分未得。后來(lái)我通過(guò)思考發(fā)現(xiàn)通過(guò)引入“物品組”和“依賴”的概念可以加深對(duì)這題的理解，還可以解決它的推廣問(wèn)題。用物品組的思想考慮那題中極其特殊的依賴關(guān)系：物品不能既作主件又作附件，每個(gè)主件最多有兩個(gè)附件，可以發(fā)現(xiàn)一個(gè)主件和它的兩個(gè)附件等價(jià)于一個(gè)由四個(gè)物品組成的物品組，這便揭示了問(wèn)題的某種本質(zhì)。
我想說(shuō)：失敗不是什么丟人的事情，從失敗中全無(wú)收獲才是。
P08: 泛化物品
定義
考慮這樣一種物品，它并沒(méi)有固定的費(fèi)用和價(jià)值，而是它的價(jià)值隨著你分配給它的費(fèi)用而變化。這就是泛化物品的概念。
更嚴(yán)格的定義之。在背包容量為V的背包問(wèn)題中，泛化物品是一個(gè)定義域?yàn)?..V中的整數(shù)的函數(shù)h，當(dāng)分配給它的費(fèi)用為v時(shí)，能得到的價(jià)值就是h(v)。
這個(gè)定義有一點(diǎn)點(diǎn)抽象，另一種理解是一個(gè)泛化物品就是一個(gè)數(shù)組h[0..V]，給它費(fèi)用v，可得到價(jià)值h[V]。
一個(gè)費(fèi)用為c價(jià)值為w的物品，如果它是01背包中的物品，那么把它看成泛化物品，它就是除了h(c)=w其它函數(shù)值都為0的一個(gè)函數(shù)。如果它是完全背包中的物品，那么它可以看成這樣一個(gè)函數(shù)，僅當(dāng)v被c整除時(shí)有h(v)=v/c*w，其它函數(shù)值均為0。如果它是多重背包中重復(fù)次數(shù)最多為n的物品，那么它對(duì)應(yīng)的泛化物品的函數(shù)有h(v)=v/c*w僅當(dāng)v被c整除且v/c<=n，其它情況函數(shù)值均為0。
一個(gè)物品組可以看作一個(gè)泛化物品h。對(duì)于一個(gè)0..V中的v，若物品組中不存在費(fèi)用為v的的物品，則h(v)=0，否則h(v)為所有費(fèi)用為v的物品的最大價(jià)值。P07中每個(gè)主件及其附件集合等價(jià)于一個(gè)物品組，自然也可看作一個(gè)泛化物品。
泛化物品的和
如果面對(duì)兩個(gè)泛化物品h和l，要用給定的費(fèi)用從這兩個(gè)泛化物品中得到最大的價(jià)值，怎么求呢？事實(shí)上，對(duì)于一個(gè)給定的費(fèi)用v，只需枚舉將這個(gè)費(fèi)用如何分配給兩個(gè)泛化物品就可以了。同樣的，對(duì)于0..V的每一個(gè)整數(shù)v，可以求得費(fèi)用v分配到h和l中的最大價(jià)值f(v)。也即f(v)=max{h(k) +l(v-k)|0<=k<=v}。可以看到，f也是一個(gè)由泛化物品h和l決定的定義域?yàn)?..V的函數(shù)，也就是說(shuō)，f是一個(gè)由泛化物品h和 l決定的泛化物品。
由此可以定義泛化物品的和：h、l都是泛化物品，若泛化物品f滿足f(v)=max{h(k)+l(v-k)|0<=k<=v}，則稱(chēng)f是h與l的和，即f=h+l。這個(gè)運(yùn)算的時(shí)間復(fù)雜度是O(V^2)。
泛化物品的定義表明：在一個(gè)背包問(wèn)題中，若將兩個(gè)泛化物品代以它們的和，不影響問(wèn)題的答案。事實(shí)上，對(duì)于其中的物品都是泛化物品的背包問(wèn)題，求它的答案的過(guò)程也就是求所有這些泛化物品之和的過(guò)程。設(shè)此和為s，則答案就是s[0..V]中的最大值。
背包問(wèn)題的泛化物品
一個(gè)背包問(wèn)題中，可能會(huì)給出很多條件，包括每種物品的費(fèi)用、價(jià)值等屬性，物品之間的分組、依賴等關(guān)系等。但肯定能將問(wèn)題對(duì)應(yīng)于某個(gè)泛化物品。也就是說(shuō)，給定了所有條件以后，就可以對(duì)每個(gè)非負(fù)整數(shù)v求得：若背包容量為v，將物品裝入背包可得到的最大價(jià)值是多少，這可以認(rèn)為是定義在非負(fù)整數(shù)集上的一件泛化物品。這個(gè)泛化物品——或者說(shuō)問(wèn)題所對(duì)應(yīng)的一個(gè)定義域?yàn)榉秦?fù)整數(shù)的函數(shù)——包含了關(guān)于問(wèn)題本身的高度濃縮的信息。一般而言，求得這個(gè)泛化物品的一個(gè)子域（例如0..V）的值之后，就可以根據(jù)這個(gè)函數(shù)的取值得到背包問(wèn)題的最終答案。
綜上所述，一般而言，求解背包問(wèn)題，即求解這個(gè)問(wèn)題所對(duì)應(yīng)的一個(gè)函數(shù)，即該問(wèn)題的泛化物品。而求解某個(gè)泛化物品的一種方法就是將它表示為若干泛化物品的和然后求之。
小結(jié)
本講可以說(shuō)都是我自己的原創(chuàng)思想。具體來(lái)說(shuō)，是我在學(xué)習(xí)函數(shù)式編程的 Scheme 語(yǔ)言時(shí)，用函數(shù)編程的眼光審視各類(lèi)背包問(wèn)題得出的理論。這一講真的很抽象，也許在“模型的抽象程度”這一方面已經(jīng)超出了NOIP的要求，所以暫且看不懂也沒(méi)關(guān)系。相信隨著你的OI之路逐漸延伸，有一天你會(huì)理解的。
我想說(shuō)：“思考”是一個(gè)OIer最重要的品質(zhì)。簡(jiǎn)單的問(wèn)題，深入思考以后，也能發(fā)現(xiàn)更多。
P09: 背包問(wèn)題問(wèn)法的變化
以上涉及的各種背包問(wèn)題都是要求在背包容量（費(fèi)用）的限制下求可以取到的最大價(jià)值，但背包問(wèn)題還有很多種靈活的問(wèn)法，在這里值得提一下。但是我認(rèn)為，只要深入理解了求背包問(wèn)題最大價(jià)值的方法，即使問(wèn)法變化了，也是不難想出算法的。
例如，求解最多可以放多少件物品或者最多可以裝滿多少背包的空間。這都可以根據(jù)具體問(wèn)題利用前面的方程求出所有狀態(tài)的值（f數(shù)組）之后得到。
還有，如果要求的是“總價(jià)值最小”“總件數(shù)最小”，只需簡(jiǎn)單的將上面的狀態(tài)轉(zhuǎn)移方程中的max改成min即可。
下面說(shuō)一些變化更大的問(wèn)法。
輸出方案
一般而言，背包問(wèn)題是要求一個(gè)最優(yōu)值，如果要求輸出這個(gè)最優(yōu)值的方案，可以參照一般動(dòng)態(tài)規(guī)劃問(wèn)題輸出方案的方法：記錄下每個(gè)狀態(tài)的最優(yōu)值是由狀態(tài)轉(zhuǎn)移方程的哪一項(xiàng)推出來(lái)的，換句話說(shuō)，記錄下它是由哪一個(gè)策略推出來(lái)的。便可根據(jù)這條策略找到上一個(gè)狀態(tài)，從上一個(gè)狀態(tài)接著向前推即可。
還是以01背包為例，方程為f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。再用一個(gè)數(shù)組g[i] [v]，設(shè)g[i][v]=0表示推出f[i][v]的值時(shí)是采用了方程的前一項(xiàng)（也即f[i][v]=f[i-1][v]），g[i][v]表示采用了方程的后一項(xiàng)。注意這兩項(xiàng)分別表示了兩種策略：未選第i個(gè)物品及選了第i個(gè)物品。那么輸出方案的偽代碼可以這樣寫(xiě)（設(shè)最終狀態(tài)為f[N][V]）：
i=N
v=V
while(i>0)
if(g[i][v]==0)
print "未選第i項(xiàng)物品"
else if(g[i][v]==1)
print "選了第i項(xiàng)物品"
v=v-c[i]
另外，采用方程的前一項(xiàng)或后一項(xiàng)也可以在輸出方案的過(guò)程中根據(jù)f[i][v]的值實(shí)時(shí)地求出來(lái)，也即不須紀(jì)錄g數(shù)組，將上述代碼中的g[i] [v]==0改成f[i][v]==f[i-1][v]，g[i][v]==1改成f[i][v]==f[i-1][v-c[i]]+w[i]也可。
輸出字典序最小的最優(yōu)方案
這里“字典序最小”的意思是1..N號(hào)物品的選擇方案排列出來(lái)以后字典序最小。以輸出01背包最小字典序的方案為例。
一般而言，求一個(gè)字典序最小的最優(yōu)方案，只需要在轉(zhuǎn)移時(shí)注意策略。首先，子問(wèn)題的定義要略改一些。我們注意到，如果存在一個(gè)選了物品1的最優(yōu)方案，那么答案一定包含物品1，原問(wèn)題轉(zhuǎn)化為一個(gè)背包容量為v-c[1]，物品為2..N的子問(wèn)題。反之，如果答案不包含物品1，則轉(zhuǎn)化成背包容量仍為V，物品為2..N的子問(wèn)題。不管答案怎樣，子問(wèn)題的物品都是以i..N而非前所述的1..i的形式來(lái)定義的，所以狀態(tài)的定義和轉(zhuǎn)移方程都需要改一下。但也許更簡(jiǎn)易的方法是先把物品逆序排列一下，以下按物品已被逆序排列來(lái)敘述。
在這種情況下，可以按照前面經(jīng)典的狀態(tài)轉(zhuǎn)移方程來(lái)求值，只是輸出方案的時(shí)候要注意：從N到1輸入時(shí)，如果f[i][v]==f[i-v]及f[i][v]==f[i-1][f-c[i]]+w[i]同時(shí)成立，應(yīng)該按照后者（即選擇了物品i）來(lái)輸出方案。
求方案總數(shù)
對(duì)于一個(gè)給定了背包容量、物品費(fèi)用、物品間相互關(guān)系（分組、依賴等）的背包問(wèn)題，除了再給定每個(gè)物品的價(jià)值后求可得到的最大價(jià)值外，還可以得到裝滿背包或?qū)⒈嘲b至某一指定容量的方案總數(shù)。
對(duì)于這類(lèi)改變問(wèn)法的問(wèn)題，一般只需將狀態(tài)轉(zhuǎn)移方程中的max改成sum即可。例如若每件物品均是01背包中的物品，轉(zhuǎn)移方程即為f[i][v]=sum{f[i-1][v],f[i-1][v-c[i]]+w[i]}，初始條件f[0][0]=1。
事實(shí)上，這樣做可行的原因在于狀態(tài)轉(zhuǎn)移方程已經(jīng)考察了所有可能的背包組成方案。
最優(yōu)方案的總數(shù)
這里的最優(yōu)方案是指物品總價(jià)值最大的方案。還是以01背包為例。
結(jié)合求最大總價(jià)值和方案總數(shù)兩個(gè)問(wèn)題的思路，最優(yōu)方案的總數(shù)可以這樣求：f[i][v]意義同前述，g[i][v]表示這個(gè)子問(wèn)題的最優(yōu)方案的總數(shù)，則在求f[i][v]的同時(shí)求g[i][v]的偽代碼如下：
for i=1..N
for v=0..V
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
g[i][v]=0
if(f[i][v]==f[i-1][v])
inc(g[i][v],g[i-1][v]
if(f[i][v]==f[i-1][v-c[i]]+w[i])
inc(g[i][v],g[i-1][v-c[i]])
如果你是第一次看到這樣的問(wèn)題，請(qǐng)仔細(xì)體會(huì)上面的偽代碼。
小結(jié)
顯然，這里不可能窮盡背包類(lèi)動(dòng)態(tài)規(guī)劃問(wèn)題所有的問(wèn)法。甚至還存在一類(lèi)將背包類(lèi)動(dòng)態(tài)規(guī)劃問(wèn)題與其它領(lǐng)域（例如數(shù)論、圖論）結(jié)合起來(lái)的問(wèn)題，在這篇論背包問(wèn)題的專(zhuān)文中也不會(huì)論及。但只要深刻領(lǐng)會(huì)前述所有類(lèi)別的背包問(wèn)題的思路和狀態(tài)轉(zhuǎn)移方程，遇到其它的變形問(wèn)法，只要題目難度還屬于NOIP，應(yīng)該也不難想出算法。