#title P09: 背包問(wèn)題問(wèn)法的變化以上涉及的各種背包問(wèn)題都是要求在背包容量（費(fèi)用）的限制下求可以取到的最大價(jià)值，但背包問(wèn)題還有很多種靈活的問(wèn)法，在這里值得提一下。但是我認(rèn)為，只要深入理解了求背包問(wèn)題最大價(jià)值的方法，即使問(wèn)法變化了，也是不難想出算法的。例如，求解最多可以放多少件物品或者最多可以裝滿(mǎ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背包為例，方程為<code>f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}</code>。再用一個(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]）：<src>i=Nv=Vwhile(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]</src>另外，采用方程的前一項(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è)背包容量為<literal>v-c[1]</literal>，物品為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-1][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)系（分組、依賴(lài)等）的背包問(wèn)題，除了再給定每個(gè)物品的價(jià)值后求可得到的最大價(jià)值外，還可以得到裝滿(mǎn)背包或?qū)⒈嘲b至某一指定容量的方案總數(shù)。對(duì)于這類(lèi)改變問(wèn)法的問(wèn)題，一般只需將狀態(tài)轉(zhuǎn)移方程中的max改成sum即可。例如若每件物品均是完全背包中的物品，轉(zhuǎn)移方程即為    <code>f[i][v]=sum{f[i-1][v],f[i][v-c[i]]}</code>初始條件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]的偽代碼如下：<src>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]])</src>如果你是第一次看到這樣的問(wèn)題，請(qǐng)仔細(xì)體會(huì)上面的偽代碼。* 求次優(yōu)解、第K優(yōu)解對(duì)于求次優(yōu)解、第K優(yōu)解類(lèi)的問(wèn)題，如果相應(yīng)的最優(yōu)解問(wèn)題能寫(xiě)出狀態(tài)轉(zhuǎn)移方程、用動(dòng)態(tài)規(guī)劃解決，那么求次優(yōu)解往往可以相同的復(fù)雜度解決，第K優(yōu)解則比求最優(yōu)解的復(fù)雜度上多一個(gè)系數(shù)K。其基本思想是將每個(gè)狀態(tài)都表示成有序隊(duì)列，將狀態(tài)轉(zhuǎn)移方程中的max/min轉(zhuǎn)化成有序隊(duì)列的合并。這里仍然以01背包為例講解一下。首先看01背包求最優(yōu)解的狀態(tài)轉(zhuǎn)移方程：<code>f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}</code>。如果要求第K優(yōu)解，那么狀態(tài)f[i][v]就應(yīng)該是一個(gè)大小為K的數(shù)組f[i][v][1..K]。其中f[i][v][k]表示前i個(gè)物品、背包大小為v時(shí)，第k優(yōu)解的值。“f[i][v]是一個(gè)大小為K的數(shù)組”這一句，熟悉C語(yǔ)言的同學(xué)可能比較好理解，或者也可以簡(jiǎn)單地理解為在原來(lái)的方程中加了一維。顯然f[i][v][1..K]這K個(gè)數(shù)是由大到小排列的，所以我們把它認(rèn)為是一個(gè)有序隊(duì)列。然后原方程就可以解釋為：f[i][v]這個(gè)有序隊(duì)列是由f[i-1][v]和f[i-1][v-c[i]]+w[i]這兩個(gè)有序隊(duì)列合并得到的。有序隊(duì)列f[i-1][v]即f[i-1][v][1..K]，f[i-1][v-c[i]]+w[i]則理解為在f[i-1][v-c[i]][1..K]的每個(gè)數(shù)上加上w[i]后得到的有序隊(duì)列。合并這兩個(gè)有序隊(duì)列并將結(jié)果的前K項(xiàng)儲(chǔ)存到f[i][v][1..K]中的復(fù)雜度是O(K)。最后的答案是f[N][V][K]。總的復(fù)雜度是O(VNK)。為什么這個(gè)方法正確呢？實(shí)際上，一個(gè)正確的狀態(tài)轉(zhuǎn)移方程的求解過(guò)程遍歷了所有可用的策略，也就覆蓋了問(wèn)題的所有方案。只不過(guò)由于是求最優(yōu)解，所以其它在任何一個(gè)策略上達(dá)不到最優(yōu)的方案都被忽略了。如果把每個(gè)狀態(tài)表示成一個(gè)大小為K的數(shù)組，并在這個(gè)數(shù)組中有序的保存該狀態(tài)可取到的前K個(gè)最優(yōu)值。那么，對(duì)于任兩個(gè)狀態(tài)的max運(yùn)算等價(jià)于兩個(gè)由大到小的有序隊(duì)列的合并。另外還要注意題目對(duì)于“第K優(yōu)解”的定義，將策略不同但權(quán)值相同的兩個(gè)方案是看作同一個(gè)解還是不同的解。如果是前者，則維護(hù)有序隊(duì)列時(shí)要保證隊(duì)列里的數(shù)沒(méi)有重復(fù)的。* 小結(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)該也不難想出算法。觸類(lèi)旁通、舉一反三，應(yīng)該也是一個(gè)OIer應(yīng)有的品質(zhì)吧。[[Index][首頁(yè)]]--------Copyright (c)  2007  Tianyi CuiPermission is granted to copy, distribute and/or modify this document under the terms of the [[http://www.gnu.org/licenses/fdl.txt][GNU Free Documentation License]], Version 1.2 or any later version published by the Free Software Foundation.