nbhkdz.com冰点文库

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

时间:2012-05-14


P05: 二维费用的背包问题
问题
二维费用的背包问题是指:对于每件物品,具有两种不同的费用;选择 这件物品必须同时付出这两种代价; 对于每种代价都有一个可付出的最 大值(背包容量) 。问怎样选择物品可以得到最大的价值。设这两种代 价分别为代价1和代价2,第 i 件物品所需的两种代价分别为 a[i]和 b[i]。两种代价可付出的最大值(两种背包容量)分别为 V 和 U。物品 的价值为 w[i]。

算法
费用加了一维, 只需状态也加一维即可。 f[i][v][u]表示前 i 件物品 设 付出两种代价分别为 v 和 u 时可获得的最大价值。状态转移方程就是:

f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}

如前述方法,可以只使用二维的数组:当每件物品只可以取一次时变量 v 和 u 采用逆序的循环,当物品有如完全背包问题时采用顺序的循环。 当物品有如多重背包问题时拆分物品。这里就不再给出伪代码了,相信 有了前面的基础,你能够自己实现出这个问题的程序。

物品总个数的限制
有时,“二维费用”的条件是以这样一种隐含的方式给出的:最多只能 取 M 件物品。这事实上相当于每件物品多了一种“件数”的费用,每个

物品的件数费用均为1,可以付出的最大件数费用为 M。换句话说,设 f[v][m]表示付出费用 v、 最多选 m 件时可得到的最大价值, 则根据物品 的类型 (01、 完全、 多重) 用不同的方法循环更新, 最后在 f[0..V][0..M] 范围内寻找答案。

复数域上的背包问题
另一种看待二维背包问题的思路是:将它看待成复数域上的背包问题。 也就是说,背包的容量以及每件物品的费用都是一个复数。而常见的一 维背包问题则是实数域上的背包问题。 (注意:上面的话其实不严谨, 因为事实上我们处理的都只是整数而已。 )所以说,一维背包的种种思 想方法,往往可以应用于二位背包问题的求解中,因为只是数域扩大了 而已。

作为这种思想的练习,你可以尝试将 P11中提到的“子集和问题”扩展 到复数域(即二维) ,并试图用同样的复杂度解决。

小结
当发现由熟悉的动态规划题目变形得来的题目时, 在原来的状态中加一 纬以满足新的限制是一种比较通用的方法。 希望你能从本讲中初步体会 到这种方法。


赞助商链接

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

但只要深刻领会前述所有 类别的背包问题的思路和状态转移方程,遇到其它的变形问...4背包问题九讲之混合三种... 5背包问题九讲之二维费用... 6背包问题九讲之...

背包九讲完整版

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

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

背包问题九讲和源程序(答案).txt 台湾一日不收复,我一日不过 4 级!如果太阳...第五讲 二维费用的背包问题 一个简单的常见扩展。 第六讲 分组的背包问题 一...

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

背包问题九讲 v1.0 目录 第一讲 01 背包问题 这是最基本的背包问题,每个...第五讲 二维费用的背包问题 一个简单的常见扩展。 第六讲 分组的背包问题 一...

绝对经典背包九讲完整版

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

背包问题九讲_v1

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

背包问题九讲 v1

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

背包问题九讲_DOC版

五讲 二维费用的背包问题 第六讲 分组的背包问题 第七讲 有依赖的背包问题 第八讲 泛化物品 第九讲 背包问题问法的变化 附:USACO 中的背包问题 前言本篇...

背包问题九讲1.0

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

背包九讲完整版

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