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背包、完全背包、多重背包都不是什么难题,但将它们简单地组合起来以后就得到了这样一道一定能吓倒不少人的题目。但只要基础扎实,领会三种基本背包问题的思想,就可以做到把困难的题目拆分成简单的题目来解决。
分享到:
相关推荐
背包九讲: P01:01背包问题 P02:完全背包问题 P03:多重背包问题 P04:混合三种背包问题 P05:二维费用的背包问题 P06:分组的背包问题 P07:有依赖的背包问题 P08:泛化物品 P09:背包问题问法的变化
算法-动态规划- 背包问题 P04- 混合背包(包含源程序).rar
1. 实验目的 2. 实验设备及工具 3. 实验准备工作 4. 实验内容 5. 实验报告要求 6. 特别提醒(重要)
P04: udevice.exe 0053000a 00000000 00010000 0000000b P05: udevice.exe 02730006 00000000 00010000 0000000b P06: explorer.exe 04a10002 00000000 00010000 00000000 P07: servicesd.exe 04d60002 00000000...
XLog2.10-R0206P04.zip
Arduino项目开发 StarterKit_BasicKit_p04_ColorMixingLamp_p04_ColorMixingLamp.pdf 学习资料 复习资料 教学资源
SUD50P04-13L-GE3-VB一种P沟道TO252封装MOS管
OC_P04_LaChouetteAgence:Projet 4 de la compositiondéveloppeurweb
Powerful Animation Editor for animating any type of 3D model right inside Unity. Reduce development time by fine tuning animations even while being in play mode. No CPU overhead: UMotion produces ...
QRes:重大项目p04
软件名称:H3C_S5500SI-CMW520-R2221P04 版本软件及说明书 发布日期:2014-7-24 15:53:46
P04-IRIS数据集.ipynb
P04A Spring 2020 - 当天所有面试问题及解决方案 每周,我都会发布我遇到或提供给候选人的常见面试问题的解决方案。 我会尽量保持下面的问题列表是最新的! ():给定一系列天数的股票价格列表,通过执行单笔交易(一...
UMotion Pro - Animation Editor 1.28p04
丰田技术员03p04.pdf
H3C S12500系列路由交换机 配置指导-R1828P04-6W182 (1).chm
SH69P04是中颖电子(Sinowealth)本着丰富USB产品应用,降低USB IC成本而设计的4BIT OTP单片机, 用以开发USB DEVICE设备。 SH69P04的功能及特点 如图1, SH69P04集成了USB SIE, 支持USB和PS2端口复用。 ...
1.1.1功能分析本项目要求对N皇后问题求解,最直接的功能就是(1)输出所有的解题方案 1.2文件目录(1)P04_1652677_吴桐欣_说明文档.docx
HM70P04K-VB一款P沟道TO252封装MOSFET应用分析
H3C SecPath F100 C II &F100 C EI CMW3 40 R5102P04 版本软件 固件 及说明书