nbhkdz.com冰点文库

4背包问题九讲之混合三种背包问题

时间:2017-07-28


P04: 混合三种背包问题
问题
如果将 P01、 P02、 P03混合起来。 也就是说, 有的物品只可以取一次 (01 背包) ,有的物品可以取无限次(完全背包) ,有的物品可以取的次数有 一个上限(多重背包) 。应该怎么求解呢?

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背包、完全 背包、多重背包都不是什么难题,但将它们简单地组合起来以后就得到 了这样一道一定能吓倒不少人的题目。但只要基础扎实,领会三种基本 背包问题的思想,就可以做到把困难的题目拆分成简单的题目来解决。


背包问题九讲和源程序(答案)

背包问题九讲和源程序(答案).txt 台湾一日不收复,我一日不过 4 级!如果太阳...第四讲 混合三种背包问题 将前面三种简单的问题叠加成较复杂的问题。 第五讲 ...

背包问题九讲

4页 免费 C++排序算法全集 19页 1财富值 0-1背包问题 算法设计C++ 3页 免费...P04: 混合三种背包问题问题如果将 P01,P02,P03 混合起来.也就是,有的物品...

7背包问题九讲之有依赖的背包问题

4背包问题九讲之混合三种背... 2页 1财富值 背包问题九讲 2.0 16页 免费 背包问题九讲 22页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或...

5背包问题九讲之二维费用的背包问题

P05: 二维费用的背包问题问题二维费用的背包问题是指:对于每件物品,具有两种不...2背包问题九讲之完全背包... 4背包问题九讲之混合三种... 6背包问题九讲之...

背包九讲

4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请...混合三种背包问题 P05: 二维费用的背包问题 P06: 分组的背包问题 P07: 有依赖...