#title P09: 背包問題問法的變化以上涉及的各種背包問題都是要求在背包容量（費用）的限制下求可以取到的最大價值，但背包問題還有很多種靈活的問法，在這里值得提一下。但是我認為，只要深入理解了求背包問題最大價值的方法，即使問法變化了，也是不難想出算法的。例如，求解最多可以放多少件物品或者最多可以裝滿多少背包的空間。這都可以根據具體問題利用前面的方程求出所有狀態的值（f數組）之后得到。還有，如果要求的是“總價值最小”“總件數最小”，只需簡單的將上面的狀態轉移方程中的max改成min即可。下面說一些變化更大的問法。* 輸出方案一般而言，背包問題是要求一個最優值，如果要求輸出這個最優值的方案，可以參照一般動態規劃問題輸出方案的方法：記錄下每個狀態的最優值是由狀態轉移方程的哪一項推出來的，換句話說，記錄下它是由哪一個策略推出來的。便可根據這條策略找到上一個狀態，從上一個狀態接著向前推即可。還是以01背包為例，方程為<code>f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}</code>。再用一個數組g[i][v]，設g[i][v]=0表示推出f[i][v]的值時是采用了方程的前一項（也即f[i][v]=f[i-1][v]），g[i][v]表示采用了方程的后一項。注意這兩項分別表示了兩種策略：未選第i個物品及選了第i個物品。那么輸出方案的偽代碼可以這樣寫（設最終狀態為f[N][V]）：<src>i=Nv=Vwhile(i>0)    if(g[i][v]==0)        print "未選第i項物品"    else if(g[i][v]==1)        print "選了第i項物品"        v=v-c[i]</src>另外，采用方程的前一項或后一項也可以在輸出方案的過程中根據f[i][v]的值實時地求出來，也即不須紀錄g數組，將上述代碼中的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]也可。* 輸出字典序最小的最優方案這里“字典序最小”的意思是1..N號物品的選擇方案排列出來以后字典序最小。以輸出01背包最小字典序的方案為例。一般而言，求一個字典序最小的最優方案，只需要在轉移時注意策略。首先，子問題的定義要略改一些。我們注意到，如果存在一個選了物品1的最優方案，那么答案一定包含物品1，原問題轉化為一個背包容量為<literal>v-c[1]</literal>，物品為2..N的子問題。反之，如果答案不包含物品1，則轉化成背包容量仍為V，物品為2..N的子問題。不管答案怎樣，子問題的物品都是以i..N而非前所述的1..i的形式來定義的，所以狀態的定義和轉移方程都需要改一下。但也許更簡易的方法是先把物品逆序排列一下，以下按物品已被逆序排列來敘述。在這種情況下，可以按照前面經典的狀態轉移方程來求值，只是輸出方案的時候要注意：從N到1輸入時，如果f[i][v]==f[i-1][i-v]及f[i][v]==f[i-1][f-c[i]]+w[i]同時成立，應該按照后者（即選擇了物品i）來輸出方案。* 求方案總數對于一個給定了背包容量、物品費用、物品間相互關系（分組、依賴等）的背包問題，除了再給定每個物品的價值后求可得到的最大價值外，還可以得到裝滿背包或將背包裝至某一指定容量的方案總數。對于這類改變問法的問題，一般只需將狀態轉移方程中的max改成sum即可。例如若每件物品均是完全背包中的物品，轉移方程即為    <code>f[i][v]=sum{f[i-1][v],f[i][v-c[i]]}</code>初始條件f[0][0]=1。事實上，這樣做可行的原因在于狀態轉移方程已經考察了所有可能的背包組成方案。* 最優方案的總數這里的最優方案是指物品總價值最大的方案。以01背包為例。結合求最大總價值和方案總數兩個問題的思路，最優方案的總數可以這樣求：f[i][v]意義同前述，g[i][v]表示這個子問題的最優方案的總數，則在求f[i][v]的同時求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>如果你是第一次看到這樣的問題，請仔細體會上面的偽代碼。* 求次優解、第K優解對于求次優解、第K優解類的問題，如果相應的最優解問題能寫出狀態轉移方程、用動態規劃解決，那么求次優解往往可以相同的復雜度解決，第K優解則比求最優解的復雜度上多一個系數K。其基本思想是將每個狀態都表示成有序隊列，將狀態轉移方程中的max/min轉化成有序隊列的合并。這里仍然以01背包為例講解一下。首先看01背包求最優解的狀態轉移方程：<code>f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}</code>。如果要求第K優解，那么狀態f[i][v]就應該是一個大小為K的數組f[i][v][1..K]。其中f[i][v][k]表示前i個物品、背包大小為v時，第k優解的值。“f[i][v]是一個大小為K的數組”這一句，熟悉C語言的同學可能比較好理解，或者也可以簡單地理解為在原來的方程中加了一維。顯然f[i][v][1..K]這K個數是由大到小排列的，所以我們把它認為是一個有序隊列。然后原方程就可以解釋為：f[i][v]這個有序隊列是由f[i-1][v]和f[i-1][v-c[i]]+w[i]這兩個有序隊列合并得到的。有序隊列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]的每個數上加上w[i]后得到的有序隊列。合并這兩個有序隊列并將結果的前K項儲存到f[i][v][1..K]中的復雜度是O(K)。最后的答案是f[N][V][K]。總的復雜度是O(VNK)。為什么這個方法正確呢？實際上，一個正確的狀態轉移方程的求解過程遍歷了所有可用的策略，也就覆蓋了問題的所有方案。只不過由于是求最優解，所以其它在任何一個策略上達不到最優的方案都被忽略了。如果把每個狀態表示成一個大小為K的數組，并在這個數組中有序的保存該狀態可取到的前K個最優值。那么，對于任兩個狀態的max運算等價于兩個由大到小的有序隊列的合并。另外還要注意題目對于“第K優解”的定義，將策略不同但權值相同的兩個方案是看作同一個解還是不同的解。如果是前者，則維護有序隊列時要保證隊列里的數沒有重復的。* 小結顯然，這里不可能窮盡背包類動態規劃問題所有的問法。甚至還存在一類將背包類動態規劃問題與其它領域（例如數論、圖論）結合起來的問題，在這篇論背包問題的專文中也不會論及。但只要深刻領會前述所有類別的背包問題的思路和狀態轉移方程，遇到其它的變形問法，只要題目難度還屬于NOIP，應該也不難想出算法。觸類旁通、舉一反三，應該也是一個OIer應有的品質吧。[[Index][首頁]]--------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.