【輸出方案】

一般而言，背包問題是要求一個最優值，如果要求輸出這個最優值的方案，可以參照一般動態規劃問題輸出方案的方法：記錄下每個狀態的最優值是由狀態轉移方程的哪一項推出來的，換句話說，記錄下它是由哪一個策略推出來的。便可根據這條策略找到上一個狀態，從上一個狀態接著向前推即可。

還是以01背包為例，方程為f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}。再用一個數組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]*/ i=N v=V while(i>0)if(g[i][v]==0)print "未選第i項物品"else if(g[i][v]==1)print "選了第i項物品"v=v-c[i]

另外，采用方程的前一項或后一項也可以在輸出方案的過程中根據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-w[i]]+c[i]。

【輸出字典序最小的最優方案】

這里“字典序最小”的意思是1..N號物品的選擇方案排列出來以后字典序最小。

以輸出01背包最小字典序的方案為例。

一般而言，求一個字典序最小的最優方案，只需要在轉移時注意策略。

首先，子問題的定義要略改一些。我們注意到，如果存在一個選了物品1的最優方案，那么答案一定包含物品1，原問題轉化為一個背包容量為v-w[1]，物品為2..N的子問題。

反之，如果答案不包含物品1，則轉化成背包容量仍為V，物品為2..N的子問題。

不管答案怎樣，子問題的物品都是以i..N而非前所述的1..i的形式來定義的，所以狀態的定義和轉移方程都需要改一下。但也許更簡易的方法是先把物品逆序排列一下，以下按物品已被逆序排列來敘述。

在這種情況下，可以按照前面經典的狀態轉移方程來求值，只是輸出方案的時候要注意：從N到1輸入時，如果f[i][v]==f[i-v]及f[i][v]==f[i-1][f-c[i]]+w[i]同時成立，應該按照后者（即選擇了物品i）來輸出方案。

【求方案總數】

對于一個給定了背包容量、物品費用、物品間相互關系（分組、依賴等）的背包問題，除了再給定每個物品的價值后求可得到的最大價值外，還可以得到裝滿背包或將背包裝至某一指定容量的方案總數。

對于這類改變問法的問題，一般只需將狀態轉移方程中的max改成sum即可。

例如若每件物品均是完全背包中的物品，轉移方程為：f[i][v]=sum{f[i-1][v],f[i][v-w[i]]}，初始條件：f[0][0]=1。

事實上，這樣做可行的原因在于狀態轉移方程已經考察了所有可能的背包組成方案。

【最優方案的總數】

這里的最優方案是指物品總價值最大的方案。

以01背包為例。

結合求最大總價值和方案總數兩個問題的思路，最優方案的總數可以這樣求：f[i][v]意義同前述，g[i][v]表示這個子問題的最優方案的總數，則在求f[i][v]的同時求g[i][v]的偽代碼如下：

for i=1..Nfor v=0..V{ f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}g[i][v]=0if(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]])}

【求次優解、第K優解】

對于求次優解、第K優解類的問題，如果相應的最優解問題能寫出狀態轉移方程、用動態規劃解決，那么求次優解往往可以相同的復雜度解決，第K優解則比求最優解的復雜度上多一個系數K。

其基本思想是將每個狀態都表示成有序隊列，將狀態轉移方程中的max/min轉化成有序隊列的合并。

這里仍然以01背包為例。

首先看01背包求最優解的狀態轉移方程：f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}。如果要求第K優解，那么狀態f[i][v]就應該是一個大小為K的數組f[i][v][1..K]。其中f[i][v][k]表示前i個物品、背包大小為v時，第k優解的值。

“f[i][v]是一個大小為K的數組”可以簡單地理解為在原來的方程中加了一維。顯然f[i][v][1..K]這K個數是由大到小排列的，所以我們把它認為是一個有序隊列。

然后原方程就可以解釋為：f[i][v]這個有序隊列是由f[i-1][v]和f[i-1][v-w[i]]+c[i]這兩個有序隊列合并得到的。有序隊列f[i-1][v]即f[i-1][v][1..K]，f[i-1][v-w[i]]+c[i]則理解為在f[i-1][v-w[i]][1..K]的每個數上加上c[i]后得到的有序隊列。

合并這兩個有序隊列并將結果（的前K項）儲存到f[i][v][1..K]中的復雜度是O(K)。最后的答案是f[N][V][K]。總的復雜度是O(NVK)。

實際上，一個正確的狀態轉移方程的求解過程遍歷了所有可用的策略，也就覆蓋了問題的所有方案。只不過由于是求最優解，所以其它在任何一個策略上達不到最優的方案都被忽略了。如果把每個狀態表示成一個大小為K的數組，并在這個數組中有序的保存該狀態可取到的前K個最優值。那么，對于任兩個狀態的max運算等價于兩個由大到小的有序隊列的合并。

另外還要注意題目對于“第K優解”的定義，將策略不同但權值相同的兩個方案是看作同一個解還是不同的解。如果是前者，則維護有序隊列時要保證隊列里的數沒有重復的。

總結

以上是生活随笔為你收集整理的动态规划 —— 背包问题 P09 —— 背包问题的变化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。