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


赞助商链接

背包问题题目及含义

DD 牛的背包九讲 P01: 01 背包问题 题目 有 N ...就将这种物品分成系数分别为 1,2,4,6 的四件物品...P04: 混合三种背包问题 问题 如果将 P01、P02、P03...

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

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

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

9背包问题九讲之背包问题文法的变化_电脑基础知识_IT/计算机_专业资料。选填,简要...2背包问题九讲之完全背包... 4背包问题九讲之混合三种... 5背包问题九讲之...

背包问题九讲_DOC版

背包问题九讲 2008.4 背包问题九讲 背包问题九讲 v1.0 目录 第一讲 01 背包问题 第二讲 完全背包问题 第三讲 多重背包问题 第四讲 混合三种背包问题 第五...

背包问题九讲+v1(深入浅出理解动态规划)

背包问题九讲 v1.0 目录 第一讲 01 背包问题 这是最基本的背包问题,每个...第四讲 混合三种背包问题 将前面三种简单的问题叠加成较复杂的问题。 第五讲 ...

背包九讲完整版

背包问题九讲 v1.0 目录 第一讲 01 背包问题 第二讲 完全背包问题 第三讲 多重背包问题 第四讲 混合三种背包问题 第五讲 二维费用的背包问题 第六讲 分组...

背包问题九讲

4 P02: 完全背包问题 ......8 P04: 混合三种背包问题 ... 8 问题... 分享到: X 分享...

绝对经典背包九讲完整版

背包问题九讲 v1.0 目录 第一讲 01 背包问题 第二讲 完全背包问题 第三讲 多重背包问题 第四讲 混合三种背包问题 第五讲 二维费用的背包问题 第六讲 分组...

背包问题九讲[1]

4 P02: 完全背包问题 ......8 P04: 混合三种背包问题 ... 8 问题......

背包问题九讲 v1

背包问题九讲 v1.0 目录 第一讲 01 背包问题 第二讲 完全背包问题 第三讲 多重背包问题 第四讲 混合三种背包问题 第五讲 二维费用的背包问题 第六讲 分组...

更多相关标签