#title P04: 混合三種背包問題* 問題如果將[[P01]]、[[P02]]、[[P03]]混合起來。也就是說，有的物品只可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數有一個上限（多重背包）。應該怎么求解呢？* 01背包與完全背包的混合考慮到在[[P01]]和[[P02]]中給出的偽代碼只有一處不同，故如果只有兩類物品：一類物品只能取一次，另一類物品可以取無限次，那么只需在對每個物品應用轉移方程時，根據物品的類別選用順序或逆序的循環即可，復雜度是O(VN)。偽代碼如下：<src>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]};</src>* 再加上多重背包如果再加上有的物品最多可以取有限次，那么原則上也可以給出O(VN)的解法：遇到多重背包類型的物品用單調隊列解即可。但如果不考慮超過NOIP范圍的算法的話，用[[P03]]中將每個這類物品分成O(log n[i])個01背包的物品的方法也已經很優了。當然，更清晰的寫法是調用我們前面給出的三個相關過程。<src>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])</src>在最初寫出這三個過程的時候，可能完全沒有想到它們會在這里混合應用。我想這體現了編程中抽象的威力。如果你一直就是以這種“抽象出過程”的方式寫每一類背包問題的，也非常清楚它們的實現中細微的不同，那么在遇到混合三種背包問題的題目時，一定能很快想到上面簡潔的解法，對嗎？* 小結有人說，困難的題目都是由簡單的題目疊加而來的。這句話是否公理暫且存之不論，但它在本講中已經得到了充分的體現。本來01背包、完全背包、多重背包都不是什么難題，但將它們簡單地組合起來以后就得到了這樣一道一定能嚇倒不少人的題目。但只要基礎扎實，領會三種基本背包問題的思想，就可以做到把困難的題目拆分成簡單的題目來解決。[[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.