P06: 分組的背包問題

問題

有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

算法

這個問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說設f[k][v]表示前k組物品花費費用v能取得的最大權值，則有：

f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i屬于第k組}

使用一維數組的偽代碼如下：

for 所有的組k

    for v=V..0

        for 所有的i屬于組k

            f[v]=max{f[v],f[v-c[i]]+w[i]}

注意這里的三層循環的順序，甚至在本文的beta版中我自己都寫錯了。“for v=V..0”這一層循環必須在“for 所有的i屬于組k”之外。這樣才能保證每一組內的物品最多只有一個會被添加到背包中。

另外，顯然可以對每組內的物品應用P02中“一個簡單有效的優化”。

小結

分組的背包問題將彼此互斥的若干物品稱為一個組，這建立了一個很好的模型。不少背包問題的變形都可以轉化為分組的背包問題（例如P07），由分組的背包問題進一步可定義“泛化物品”的概念，十分有利于解題。

首頁

P07: 有依賴的背包問題

簡化的問題

這種背包問題的物品間存在某種“依賴”的關系。也就是說，i依賴于j，表示若選物品i，則必須選物品j。為了簡化起見，我們先設沒有某個物品既依賴于別的物品，又被別的物品所依賴；另外，沒有某件物品同時依賴多件物品。

算法

這個問題由NOIP2006金明的預算方案一題擴展而來。遵從該題的提法，將不依賴于別的物品的物品稱為“主件”，依賴于某主件的物品稱為“附件”。由這個問題的簡化條件可知所有的物品由若干主件和依賴于每個主件的一個附件集合組成。

按照背包問題的一般思路，僅考慮一個主件和它的附件集合。可是，可用的策略非常多，包括：一個也不選，僅選擇主件，選擇主件后再選擇一個附件，選擇主件后再選擇兩個附件……無法用狀態轉移方程來表示如此多的策略。（事實上，設有n個附件，則策略有2^n+1個，為指數級。）

考慮到所有這些策略都是互斥的（也就是說，你只能選擇一種策略），所以一個主件和它的附件集合實際上對應于P06中的一個物品組，每個選擇了主件又選擇了若干個附件的策略對應于這個物品組中的一個物品，其費用和價值都是這個策略中的物品的值的和。但僅僅是這一步轉化并不能給出一個好的算法，因為物品組中的物品還是像原問題的策略一樣多。

再考慮P06中的一句話： 可以對每組中的物品應用P02中“一個簡單有效的優化”。 這提示我們，對于一個物品組中的物品，所有費用相同的物品只留一個價值最大的，不影響結果。所以，我們可以對主件i的“附件集合”先進行一次01背包，得到費用依次為0..V-c[i]所有這些值時相應的最大價值f'[0..V-c[i]]。那么這個主件及它的附件集合相當于V-c[i]+1個物品的物品組，其中費用為c[i]+k的物品的價值為f'[k]+w[i]。也就是說原來指數級的策略中有很多策略都是冗余的，通過一次01背包后，將主件i轉化為V-c[i]+1個物品的物品組，就可以直接應用P06的算法解決問題了。

較一般的問題

更一般的問題是：依賴關系以圖論中“森林”的形式給出（森林即多叉樹的集合），也就是說，主件的附件仍然可以具有自己的附件集合，限制只是每個物品最多只依賴于一個物品（只有一個主件）且不出現循環依賴。

解決這個問題仍然可以用將每個主件及其附件集合轉化為物品組的方式。唯一不同的是，由于附件可能還有附件，就不能將每個附件都看作一個一般的01背包中的物品了。若這個附件也有附件集合，則它必定要被先轉化為物品組，然后用分組的背包問題解出主件及其附件集合所對應的附件組中各個費用的附件所對應的價值。

事實上，這是一種樹形DP，其特點是每個父節點都需要對它的各個兒子的屬性進行一次DP以求得自己的相關屬性。這已經觸及到了“泛化物品”的思想。看完P08后，你會發現這個“依賴關系樹”每一個子樹都等價于一件泛化物品，求某節點為根的子樹對應的泛化物品相當于求其所有兒子的對應的泛化物品之和。

小結

NOIP2006的那道背包問題我做得很失敗，寫了上百行的代碼，卻一分未得。后來我通過思考發現通過引入“物品組”和“依賴”的概念可以加深對這題的理解，還可以解決它的推廣問題。用物品組的思想考慮那題中極其特殊的依賴關系：物品不能既作主件又作附件，每個主件最多有兩個附件，可以發現一個主件和它的兩個附件等價于一個由四個物品組成的物品組，這便揭示了問題的某種本質。

我想說：失敗不是什么丟人的事情，從失敗中全無收獲才是。

首頁

P08: 泛化物品

定義

考慮這樣一種物品，它并沒有固定的費用和價值，而是它的價值隨著你分配給它的費用而變化。這就是泛化物品的概念。

更嚴格的定義之。在背包容量為V的背包問題中，泛化物品是一個定義域為0..V中的整數的函數h，當分配給它的費用為v時，能得到的價值就是h(v)。

這個定義有一點點抽象，另一種理解是一個泛化物品就是一個數組h[0..V]，給它費用v，可得到價值h[V]。

一個費用為c價值為w的物品，如果它是01背包中的物品，那么把它看成泛化物品，它就是除了h(c)=w其它函數值都為0的一個函數。如果它是完全背包中的物品，那么它可以看成這樣一個函數，僅當v被c整除時有h(v)=v/c*w，其它函數值均為0。如果它是多重背包中重復次數最多為n的物品，那么它對應的泛化物品的函數有h(v)=v/c*w僅當v被c整除且v/c<=n，其它情況函數值均為0。

一個物品組可以看作一個泛化物品h。對于一個0..V中的v，若物品組中不存在費用為v的的物品，則h(v)=0，否則h(v)為所有費用為v的物品的最大價值。P07中每個主件及其附件集合等價于一個物品組，自然也可看作一個泛化物品。

泛化物品的和

如果面對兩個泛化物品h和l，要用給定的費用從這兩個泛化物品中得到最大的價值，怎么求呢？事實上，對于一個給定的費用v，只需枚舉將這個費用如何分配給兩個泛化物品就可以了。同樣的，對于0..V的每一個整數v，可以求得費用v分配到h和l中的最大價值f(v)。也即f(v)=max{h(k)+l(v-k)|0<=k<=v}。可以看到，f也是一個由泛化物品h和l決定的定義域為0..V的函數，也就是說，f是一個由泛化物品h和l決定的泛化物品。

由此可以定義泛化物品的和：h、l都是泛化物品，若泛化物品f滿足f(v)=max{h(k)+l(v-k)|0<=k<=v}，則稱f是h與l的和，即f=h+l。這個運算的時間復雜度取決于背包的容量，是O(V^2)。

泛化物品的定義表明：在一個背包問題中，若將兩個泛化物品代以它們的和，不影響問題的答案。事實上，對于其中的物品都是泛化物品的背包問題，求它的答案的過程也就是求所有這些泛化物品之和的過程。設此和為s，則答案就是s[0..V]中的最大值。

背包問題的泛化物品

一個背包問題中，可能會給出很多條件，包括每種物品的費用、價值等屬性，物品之間的分組、依賴等關系等。但肯定能將問題對應于某個泛化物品。也就是說，給定了所有條件以后，就可以對每個非負整數v求得：若背包容量為v，將物品裝入背包可得到的最大價值是多少，這可以認為是定義在非負整數集上的一件泛化物品。這個泛化物品——或者說問題所對應的一個定義域為非負整數的函數——包含了關于問題本身的高度濃縮的信息。一般而言，求得這個泛化物品的一個子域（例如0..V）的值之后，就可以根據這個函數的取值得到背包問題的最終答案。

綜上所述，一般而言，求解背包問題，即求解這個問題所對應的一個函數，即該問題的泛化物品。而求解某個泛化物品的一種方法就是將它表示為若干泛化物品的和然后求之。

小結

本講可以說都是我自己的原創思想。具體來說，是我在學習函數式編程的 Scheme 語言時，用函數編程的眼光審視各類背包問題得出的理論。這一講真的很抽象，也許在“模型的抽象程度”這一方面已經超出了NOIP的要求，所以暫且看不懂也沒關系。相信隨著你的OI之路逐漸延伸，有一天你會理解的。

我想說：“思考”是一個OIer最重要的品質。簡單的問題，深入思考以后，也能發現更多。

首頁

P09: 背包問題問法的變化

以上涉及的各種背包問題都是要求在背包容量（費用）的限制下求可以取到的最大價值，但背包問題還有很多種靈活的問法，在這里值得提一下。但是我認為，只要深入理解了求背包問題最大價值的方法，即使問法變化了，也是不難想出算法的。

例如，求解最多可以放多少件物品或者最多可以裝滿多少背包的空間。這都可以根據具體問題利用前面的方程求出所有狀態的值（f數組）之后得到。

還有，如果要求的是“總價值最小”“總件數最小”，只需簡單的將上面的狀態轉移方程中的max改成min即可。

下面說一些變化更大的問法。

輸出方案

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

還是以01背包為例，方程為f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[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-c[i]]+w[i]也可。

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

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

一般而言，求一個字典序最小的最優方案，只需要在轉移時注意策略。首先，子問題的定義要略改一些。我們注意到，如果存在一個選了物品1的最優方案，那么答案一定包含物品1，原問題轉化為一個背包容量為v-c[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-c[i]]}

初始條件f[0][0]=1。

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

最優方案的總數

這里的最優方案是指物品總價值最大的方案。以01背包為例。

結合求最大總價值和方案總數兩個問題的思路，最優方案的總數可以這樣求：f[i][v]意義同前述，g[i][v]表示這個子問題的最優方案的總數，則在求f[i][v]的同時求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]])

如果你是第一次看到這樣的問題，請仔細體會上面的偽代碼。

求次優解、第K優解

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

其基本思想是將每個狀態都表示成有序隊列，將狀態轉移方程中的max/min轉化成有序隊列的合并。這里仍然以01背包為例講解一下。

首先看01背包求最優解的狀態轉移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。如果要求第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(NVK)。

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

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

小結

顯然，這里不可能窮盡背包類動態規劃問題所有的問法。甚至還存在一類將背包類動態規劃問題與其它領域（例如數論、圖論）結合起來的問題，在這篇論背包問題的專文中也不會論及。但只要深刻領會前述所有類別的背包問題的思路和狀態轉移方程，遇到其它的變形問法，只要題目難度還屬于NOIP，應該也不難想出算法。觸類旁通、舉一反三，應該也是一個OIer應有的品質吧。

首頁

附：USACO中的背包問題

USACO是USA Computing Olympiad的簡稱，它組織了很多面向全球的計算機競賽活動。

USACO Trainng是一個很適合初學者的題庫，我認為它的特色是題目質量高，循序漸進，還配有不錯的課文和題目分析。其中關于背包問題的那篇課文 (TEXT Knapsack Problems) 也值得一看。

另外，USACO Contest是USACO常年組織的面向全球的競賽系列，在此也推薦NOIP選手參加。

我整理了USACO Training中涉及背包問題的題目，應該可以作為不錯的習題。其中標加號的是我比較推薦的，標嘆號的是我認為對NOIP選手比較有挑戰性的。

題目列表

·         Inflate (+) （基本01背包）

·         Stamps (+)(!) （對初學者有一定挑戰性）

·         Money

·         Nuggets

·         Subsets

·         Rockers (+) （另一類有趣的“二維”背包問題）

·         Milk4 (!) （很怪的背包問題問法，較難用純DP求解）

題目簡解

以下文字來自我所撰的《USACO心得》一文，該文的完整版本，包括我的程序，可在DD的USACO征程中找到。

Inflate 是加權01 背包問題，也就是說：每種物品只有一件，只可以選擇放或者不放；而且每種物品有對應的權值，目標是使總權值最大或最小。它最樸素的狀態轉移方程是：f[k][i] = max{f[k-1][i] , f[k-1][i-v[k]]+w[k]}。f[k][i]表示前k 件物品花費代價i 可以得到的最大權值。v[k]和w[k]分別是第k 件物品的花費和權值。可以看到， f[k]的求解過程就是使用第k 件物品對f[k-1]進行更新的過程。那么事實上就不用使用二維數組，只需要定義f[i]，然后對于每件物品k，順序地檢查f[i]與f[i-v[k]]+w[k]的大小，如果后者更大，就對前者進行更新。這是背包問題中典型的優化方法。

題目stamps 中，每種物品的使用量沒有直接限制，但使用物品的總量有限制。求第一個不能用這有限個物品組成的背包的大小。（可以這樣等價地認為）設f[k][i] 表示前k 件物品組成大小為i 的背包， 最少需要物品的數量。則f[k][i]= min{f[k-1][i],f[k-1][i-j*s[k]]+j}，其中j 是選擇使用第k 件物品的數目，這個方程運用時可以用和上面一樣的方法處理成一維的。求解時先設置一個粗糙的循環上限，即最大的物品乘最多物品數。

Money 是多重背包問題。也就是每個物品可以使用無限多次。要求解的是構成一種背包的不同方案總數。基本上就是把一般的多重背包的方程中的min 改成sum 就行了。

Nuggets 的模型也是多重背包。要求求解所給的物品不能恰好放入的背包大小的最大值（可能不存在）。只需要根據“若i、j 互質，則關于x、y 的不定方程i*x+y*j=n 必有正整數解，其中n>i*j”這一定理得出一個循環的上限。 Subsets 子集和問題相當于物品大小是前N 個自然數時求大小為N*(N+1)/4 的 01 背包的方案數。

Rockers 可以利用求解背包問題的思想設計解法。我的狀態轉移方程如下： f[i][j][t]=max{f[i][j][t-1] , f[i-1][j][t] , f[i-1][j][t-time[i]]+1 , f[i-1][j-1][T]+(t>=time[i])}。其中 f[i][j][t]表示前i 首歌用j 張完整的盤和一張錄了t 分鐘的盤可以放入的最多歌數，T 是一張光盤的最大容量，t>=time[i]是一個bool 值轉換成int 取值為0 或1。但我后來發現我當時設計的狀態和方程效率有點低，如果換成這樣：f[i][j]=(a,b)表示前i 首歌中選了j 首需要用到a 張完整的光盤以及一張錄了b 分鐘的光盤，會將時空復雜度都大大降低。這種將狀態的值設為二維的方法值得注意。

Milk4 是這些類背包問題中難度最大的一道了。很多人無法做到將它用純DP 方法求解，而是用迭代加深搜索枚舉使用的桶，將其轉換成多重背包問題再DP。由于 USACO 的數據弱，迭代加深的深度很小，這樣也可以AC，但我們還是可以用純DP 方法將它完美解決的。設f[k]為稱量出k 單位牛奶需要的最少的桶數。那么可以用類似多重背包的方法對f 數組反復更新以求得最小值。然而困難在于如何輸出字典序最小的方案。我們可以對每個i 記錄pre_f[i]和pre_v[i]。表示得到i 單位牛奶的過程是用pre_f[i]單位牛奶加上若干個編號為pre_v[i]的桶的牛奶。這樣就可以一步步求得得到i 單位牛奶的完整方案。為了使方案的字典序最小，我們在每次找到一個耗費桶數相同的方案時對已儲存的方案和新方案進行比較再決定是否更新方案。為了使這種比較快捷，在使用各種大小的桶對f 數組進行更新時先大后小地進行。USACO 的官方題解正是這一思路。如果認為以上文字比較難理解可以閱讀官方程序或我的程序。

首頁

Copyright (c) 2007 Tianyi Cui

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.

整理 by stntwm