#title 附：USACO中的背包問題[[http://www.usaco.org/][USACO]]是USA Computing Olympiad的簡稱，它組織了很多面向全球的計算機競賽活動。[[http://train.usaco.org/][USACO Trainng]]是一個很適合初學者的題庫，我認為它的特色是題目質量高，循序漸進，還配有不錯的課文和題目分析。其中關于背包問題的那篇課文 (TEXT Knapsack Problems) 也值得一看。另外，[[http://contest.usaco.org/][USACO Contest]]是USACO常年組織的面向全球的競賽系列，在此也推薦NOIP選手參加。我整理了USACO Training中涉及背包問題的題目，應該可以作為不錯的習題。其中標加號的是我比較推薦的，標嘆號的是我認為對NOIP選手比較有挑戰性的。* 題目列表    - Inflate (+) （基本01背包）    - Stamps (+)(!) （對初學者有一定挑戰性）    - Money    - Nuggets    - Subsets    - Rockers (+) （另一類有趣的“二維”背包問題）    - Milk4 (!) （很怪的背包問題問法，較難用純DP求解）* 題目簡解以下文字來自我所撰的《USACO心得》一文，該文的完整版本，包括我的程序，可在[[http://my.opera.com/dd-usaco/][DD的USACO征程]]中找到。<quote>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 的官方題解正是這一思路。如果認為以上文字比較難理解可以閱讀官方程序或我的程序。</quote>[[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.