前言

本篇文章是我(dd_engi)正在進行中的一個雄心勃勃的寫作計劃的一部分，這個計劃的內容是寫作一份較為完善的NOIP難度的動態規劃總結，名為《解動態規劃題的基本思考方式》?，F在你看到的是這個寫作計劃最先發布的一部分。

背包問題是一個經典的動態規劃模型。它既簡單形象容易理解，又在某種程度上能夠揭示動態規劃的本質，故不少教材都把它作為動態規劃部分的第一道例題，我也將它放在我的寫作計劃的第一部分。

讀本文最重要的是思考。因為我的語言和寫作方式向來不以易于理解為長，思路也偶有跳躍的地方，后面更有需要大量思考才能理解的比較抽象的內容。更重要的是：不大量思考，絕對不可能學好動態規劃這一信息學奧賽中最精致的部分。

你現在看到的是本文的v1.1版，發布于2007年11月15日。我會長期維護這份文本，把大家的意見和建議融入其中，也會不斷加入我在OI學習以及將來可能的ACM-ICPC的征程中得到的新的心得。但目前本文還沒有一個固定的發布頁面，想了解本文是否有更新版本發布，可以在OIBH論壇中以“背包問題九講”為關鍵字搜索貼子，每次比較重大的版本更新都會在這個論壇里發貼公布。也可以用“背包問題九講”為關鍵字在搜索引擎中搜索以得到最新版本。

P01: 01背包問題

題目

有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。

基本思路

這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。

用子問題定義狀態：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是：

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

這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉化為“前i-1件物品放入容量為v的背包中”，價值為f[i-1][v]；如果放第i件物品，那么問題就轉化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。

優化空間復雜度

以上方法的時間和空間復雜度均為O(VN)，其中時間復雜度應該已經不能再優化了，但空間復雜度卻可以優化到O。

先考慮上面講的基本思路如何實現，肯定是有一個主循環i=1..N，每次算出來二維數組f[i][0..V]的所有值。那么，如果只用一個數組f[0..V]，能不能保證第i次循環結束后f[v]中表示的就是我們定義的狀態f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環中推f[v]時）能夠得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事實上，這要求在每次主循環中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[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]]}一句恰就相當于我們的轉移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因為現在的f[v-c[i]]就相當于原來的f[i-1][v-c[i]]。如果將v的循環順序從上面的逆序改成順序的話，那么則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學習只用一維數組解01背包問題是十分必要的。

事實上，使用一維數組解01背包的程序在后面會被多次用到，所以這里抽象出一個處理一件01背包中的物品過程，以后的代碼中直接調用不加說明。

過程ZeroOnePack，表示處理一件01背包中的物品，兩個參數cost、weight分別表明這件物品的費用和價值。

procedure ZeroOnePack(cost,weight)     for v=V..cost         f[v]=max{f[v],f[v-cost]+weight}

注意這個過程里的處理與前面給出的偽代碼有所不同。前面的示例程序寫成v=V..0是為了在程序中體現每個狀態都按照方程求解了，避免不必要的思維復雜度。而這里既然已經抽象成看作黑箱的過程了，就可以加入優化。費用為cost的物品不會影響狀態f[0..cost-1]，這是顯然的。

有了這個過程以后，01背包問題的偽代碼就可以這樣寫：

for i=1..N     ZeroOnePack(c[i],w[i]);

初始化的細節問題

我們看到的求最優解的背包問題題目中，事實上有兩種不太相同的問法。有的題目要求“恰好裝滿背包”時的最優解，有的題目則并沒有要求必須把背包裝滿。一種區別這兩種問法的實現方法是在初始化的時候有所不同。

如果是第一種問法，要求恰好裝滿背包，那么在初始化時除了f[0]為0其它f[1..V]均設為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優解。

如果并沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應該將f[0..V]全部設為0。

為什么呢？可以這樣理解：初始化的f數組事實上就是在沒有任何物品可以放入背包時的合法狀態。如果要求背包恰好裝滿，那么此時只有容量為0的背包可能被價值為0的nothing“恰好裝滿”，其它容量的背包均沒有合法的解，屬于未定義的狀態，它們的值就都應該是-∞了。如果背包并非必須被裝滿，那么任何容量的背包都有一個合法解“什么都不裝”，這個解的價值為0，所以初始時狀態的值也就全部為0了。

這個小技巧完全可以推廣到其它類型的背包問題，后面也就不再對進行狀態轉移之前的初始化進行講解。

一個常數優化

前面的偽代碼中有 for v=V..1，可以將這個循環的下限進行改進。

由于只需要最后f[v]的值，倒推前一個物品，其實只要知道f[v-w[n]]即可。以此類推，對以第j個背包，其實只需要知道到f[v-sum{w[j..n]}]即可，即代碼中的

for i=1..N     for v=V..0

可以改成

for i=1..n     bound=max{V-sum{w[i..n]},c[i]}     for v=V..bound

這對于V比較大時是有用的。

小結

01背包問題是最基本的背包問題，它包含了背包問題中設計狀態、方程的最基本思想，另外，別的類型的背包問題往往也可以轉換成01背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀態轉移方程的意義，以及最后怎樣優化的空間復雜度。

P02: 完全背包問題

題目

有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

基本思路

這個問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關的策略已并非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01背包時的思路，令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值。仍然可以按照每種物品不同的策略寫出狀態轉移方程，像這樣：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

這跟01背包問題一樣有O(VN)個狀態需要求解，但求解每個狀態的時間已經不是常數了，求解狀態f[i][v]的時間是O(v/c[i])，總的復雜度可以認為是O(V*Σ(V/c[i]))，是比較大的。

將01背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問題。但我們還是試圖改進這個復雜度。

一個簡單有效的優化

完全背包問題有一個很簡單有效的優化，是這樣的：若兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j]，則將物品j去掉，不用考慮。這個優化的正確性顯然：任何情況下都可將價值小費用高得j換成物美價廉的i，得到至少不會更差的方案。對于隨機生成的數據，這個方法往往會大大減少物品的件數，從而加快速度。然而這個并不能改善最壞情況的復雜度，因為有可能特別設計的數據可以一件物品也去不掉。

這個優化可以簡單的O(N^2)地實現，一般都可以承受。另外，針對背包問題而言，比較不錯的一種方法是：首先將費用大于V的物品去掉，然后使用類似計數排序的做法，計算出費用相同的物品中價值最高的是哪個，可以O(V+N)地完成這個優化。這個不太重要的過程就不給出偽代碼了，希望你能獨立思考寫出偽代碼或程序。

轉化為01背包問題求解

既然01背包問題是最基本的背包問題，那么我們可以考慮把完全背包問題轉化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/c[i]件，于是可以把第i種物品轉化為V/c[i]件費用及價值均不變的物品，然后求解這個01背包問題。這樣完全沒有改進基本思路的時間復雜度，但這畢竟給了我們將完全背包問題轉化為01背包問題的思路：將一種物品拆成多件物品。

更高效的轉化方法是：把第i種物品拆成費用為c[i]*2^k、價值為w[i]*2^k的若干件物品，其中k滿足c[i]*2^k<=V。這是二進制的思想，因為不管最優策略選幾件第i種物品，總可以表示成若干個2^k件物品的和。這樣把每種物品拆成O(log V/c[i])件物品，是一個很大的改進。

但我們有更優的O(VN)的算法。

O(VN)的算法

這個算法使用一維數組，先看偽代碼：

for i=1..N     for v=0..V         f[v]=max{f[v],f[v-cost]+weight}

你會發現，這個偽代碼與P01的偽代碼只有v的循環次序不同而已。為什么這樣一改就可行呢？首先想想為什么P01中要按照v=V..0的逆序來循環。這是因為要保證第i次循環中的狀態f[i][v]是由狀態f[i-1][v-c[i]]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時，依據的是一個絕無已經選入第i件物品的子結果f[i-1][v-c[i]]。而現在完全背包的特點恰是每種物品可選無限件，所以在考慮“加選一件第i種物品”這種策略時，卻正需要一個可能已選入第i種物品的子結果f[i][v-c[i]]，所以就可以并且必須采用v=0..V的順序循環。這就是這個簡單的程序為何成立的道理。

值得一提的是，上面的偽代碼中兩層for循環的次序可以顛倒。這個結論有可能會帶來算法時間常數上的優化。

這個算法也可以以另外的思路得出。例如，將基本思路中求解f[i][v-c[i]]的狀態轉移方程顯式地寫出來，代入原方程中，會發現該方程可以等價地變形成這種形式：

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

將這個方程用一維數組實現，便得到了上面的偽代碼。

最后抽象出處理一件完全背包類物品的過程偽代碼：

procedure CompletePack(cost,weight)     for v=cost..V         f[v]=max{f[v],f[v-c[i]]+w[i]}

總結

完全背包問題也是一個相當基礎的背包問題，它有兩個狀態轉移方程，分別在“基本思路”以及“O(VN)的算法“的小節中給出。希望你能夠對這兩個狀態轉移方程都仔細地體會，不僅記住，也要弄明白它們是怎么得出來的，最好能夠自己想一種得到這些方程的方法。事實上，對每一道動態規劃題目都思考其方程的意義以及如何得來，是加深對動態規劃的理解、提高動態規劃功力的好方法。

P03: 多重背包問題

題目

有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

基本算法

這題目和完全背包問題很類似?；镜姆匠讨恍鑼⑼耆嘲鼏栴}的方程略微一改即可，因為對于第i種物品有n[i]+1種策略：取0件，取1件……取n[i]件。令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值，則有狀態轉移方程：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

復雜度是O(V*Σn[i])。

轉化為01背包問題

另一種好想好寫的基本方法是轉化為01背包求解：把第i種物品換成n[i]件01背包中的物品，則得到了物品數為Σn[i]的01背包問題，直接求解，復雜度仍然是O(V*Σn[i])。

但是我們期望將它轉化為01背包問題之后能夠像完全背包一樣降低復雜度。仍然考慮二進制的思想，我們考慮把第i種物品換成若干件物品，使得原問題中第i種物品可取的每種策略——取0..n[i]件——均能等價于取若干件代換以后的物品。另外，取超過n[i]件的策略必不能出現。

方法是：將第i種物品分成若干件物品，其中每件物品有一個系數，這件物品的費用和價值均是原來的費用和價值乘以這個系數。使這些系數分別為1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數。例如，如果n[i]為13，就將這種物品分成系數分別為1,2,4,6的四件物品。

分成的這幾件物品的系數和為n[i]，表明不可能取多于n[i]件的第i種物品。另外這種方法也能保證對于0..n[i]間的每一個整數，均可以用若干個系數的和表示，這個證明可以分0..2^k-1和2^k..n[i]兩段來分別討論得出，并不難，希望你自己思考嘗試一下。

這樣就將第i種物品分成了O(log n[i])種物品，將原問題轉化為了復雜度為<math>O(V*Σlog n[i])的01背包問題，是很大的改進。

下面給出O(log amount)時間處理一件多重背包中物品的過程，其中amount表示物品的數量：

procedure MultiplePack(cost,weight,amount)     if cost*amount>=V         CompletePack(cost,weight)         return     integer k=1     while k<amount         ZeroOnePack(k*cost,k*weight)         amount=amount-k         k=k*2     ZeroOnePack(amount*cost,amount*weight)

希望你仔細體會這個偽代碼，如果不太理解的話，不妨翻譯成程序代碼以后，單步執行幾次，或者頭腦加紙筆模擬一下，也許就會慢慢理解了。

O(VN)的算法

多重背包問題同樣有O(VN)的算法。這個算法基于基本算法的狀態轉移方程，但應用單調隊列的方法使每個狀態的值可以以均攤O(1)的時間求解。由于用單調隊列優化的DP已超出了NOIP的范圍，故本文不再展開講解。我最初了解到這個方法是在樓天成的“男人八題”幻燈片上。

小結

這里我們看到了將一個算法的復雜度由O(V*Σn[i])改進到O(V*Σlog n[i])的過程，還知道了存在應用超出NOIP范圍的知識的O(VN)算法。希望你特別注意“拆分物品”的思想和方法，自己證明一下它的正確性，并將完整的程序代碼寫出來。

P04: 混合三種背包問題

問題

如果將P01、P02、P03混合起來。也就是說，有的物品只可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數有一個上限（多重背包）。應該怎么求解呢？

01背包與完全背包的混合

考慮到在P01和P02中給出的偽代碼只有一處不同，故如果只有兩類物品：一類物品只能取一次，另一類物品可以取無限次，那么只需在對每個物品應用轉移方程時，根據物品的類別選用順序或逆序的循環即可，復雜度是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)的解法：遇到多重背包類型的物品用單調隊列解即可。但如果不考慮超過NOIP范圍的算法的話，用P03中將每個這類物品分成O(log n[i])個01背包的物品的方法也已經很優了。

當然，更清晰的寫法是調用我們前面給出的三個相關過程。

for i=1..N     if 第i件物品屬于01背包         ZeroOnePack(c[i],w[i])     else if 第i件物品屬于完全背包         CompletePack(c[i],w[i])     else if 第i件物品屬于多重背包         MultiplePack(c[i],w[i],n[i])

在最初寫出這三個過程的時候，可能完全沒有想到它們會在這里混合應用。我想這體現了編程中抽象的威力。如果你一直就是以這種“抽象出過程”的方式寫每一類背包問題的，也非常清楚它們的實現中細微的不同，那么在遇到混合三種背包問題的題目時，一定能很快想到上面簡潔的解法，對嗎？

小結

有人說，困難的題目都是由簡單的題目疊加而來的。這句話是否公理暫且存之不論，但它在本講中已經得到了充分的體現。本來01背包、完全背包、多重背包都不是什么難題，但將它們簡單地組合起來以后就得到了這樣一道一定能嚇倒不少人的題目。但只要基礎扎實，領會三種基本背包問題的思想，就可以做到把困難的題目拆分成簡單的題目來解決。

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以求得自己的相關屬性。這已經觸及到了“泛化物品”的思想?？赐?a target="_blank" style="text-decoration: none; color: rgb(67, 123, 64); ">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是h與l的和。這個運算的時間復雜度取決于背包的容量，是O(V^2)。

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

背包問題的泛化物品

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

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

小結

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

我想說：“思考”是一個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 是多重背包問題。也就是每個物品可以使用無限多次。要求解的是構成一種背包的不同方案總數?；旧暇褪前岩话愕亩嘀乇嘲姆匠讨械膍in 改成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 的官方題解正是這一思路。如果認為以上文字比較難理解可以閱讀官方程序或我的程序。