背包九講 P04: 混合三種背包問題

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背包、完全背包、多重背包都不是什麼難題，但将它們簡單地組合起來以後就得到了這樣一道一定能吓倒不少人的題目。但隻要基礎紮實，領會三種基本背包問題的思想，就可以做到把困難的題目拆分成簡單的題目來解決。