nbhkdz.com冰点文库

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

时间:2012-05-14


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


赞助商链接

背包问题九讲[1]

问题 3 一个常数优化 3 小结 3 P02: 完全背包问题 3 题目 3 基本思路 4 ...背包问题 5 O(VN)的算法 6 小结 6 P04: 混合三种背包问题 问题 6 01 ...

背包九讲

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

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

5背包问题九讲之二维费用的背包问题_电脑基础知识_IT/计算机_专业资料。选填,...4背包问题九讲之混合三种... 2页 1下载券 喜欢此文档的还喜欢 四川...

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

7背包问题九讲之有依赖的背包问题_电脑基础知识_IT/计算机_专业资料。选填,简要...背包问题九讲_DOC版 24页 免费 4背包问题九讲之混合三种... 2页 1下载...

9背包问题九讲之背包问题文法的变化

9背包问题九讲之背包问题文法的变化_电脑基础知识_IT/计算机_专业资料。选填,简要介绍文档的主要内容,方便文档被更多人浏览和下载。 ...

背包问题九讲(很详细)

背包问题九讲(很详细)_理学_高等教育_教育专区。...使这些系数分别为 1,2,4,...,2^(k-1),n[i...P04: 混合三种背包问题问题 如果将 P01、P02、P03 ...