Knapsack - Mixed 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]) 

在最初写出这三个过程的时候，可能完全没有想到它们会在这里混合应用。我想这体现了编程中抽象的威力。如果你一直就是以这种"抽象出过程"的方式写每一类背包问题的，也非常清楚它们的实现中细微的不同，那么在遇到混合三种背包问题的题目时，一定能很快想到上面简洁的解法，对吗？

Read full article from P04: 混合三种背包问题