背包问题九讲(ACM好东西)资源-CSDN文库

需积分: 9 194 浏览量 2010-04-28 22:35:31 上传评论收藏 132KB DOC 举报

资源推荐

资源详情

资源评论

P01: 01 背包问题................................................................................................................................2
题目.............................................................................................................................................2
基本思路.....................................................................................................................................2
优化空间复杂度.........................................................................................................................2
初始化的细节问题.....................................................................................................................3
一个常数优化.............................................................................................................................4
小结.............................................................................................................................................4
P02: 完全背包问题.............................................................................................................................4
题目.............................................................................................................................................4
基本思路.....................................................................................................................................5
一个简单有效的优化.................................................................................................................5
转化为 01 背包问题求解...........................................................................................................5
O(VN)的算法..............................................................................................................................6
总结.............................................................................................................................................7
P03: 多重背包问题.............................................................................................................................7
题目.............................................................................................................................................7
基本算法.....................................................................................................................................7
转化为 01 背包问题...................................................................................................................7
O(VN)的算法..............................................................................................................................8
小结.............................................................................................................................................8
P04: 混合三种背包问题....................................................................................................................8
问题.............................................................................................................................................8
01 背包与完全背包的混合........................................................................................................9
再加上多重背包.........................................................................................................................9
小结.............................................................................................................................................9
P05: 二维费用的背包问题..............................................................................................................10
问题...........................................................................................................................................10
算法...........................................................................................................................................10
物品总个数的限制...................................................................................................................10
复数域上的背包问题...............................................................................................................10
小结...........................................................................................................................................11
P06: 分组的背包问题.......................................................................................................................11
问题...........................................................................................................................................11
算法...........................................................................................................................................11
小结...........................................................................................................................................11
P07: 有依赖的背包问题..................................................................................................................12
简化的问题...............................................................................................................................12
算法...........................................................................................................................................12
较一般的问题...........................................................................................................................12
小结...........................................................................................................................................13
P08: 泛化物品...................................................................................................................................13
定义...........................................................................................................................................13
泛化物品的和...........................................................................................................................14
背包问题的泛化物品...............................................................................................................14

小结...........................................................................................................................................15

P09: 背包问题问法的变化..............................................................................................................15

输出方案...................................................................................................................................15

输出字典序最小的最优方案...................................................................................................16

求方案总数...............................................................................................................................16

最优方案的总数.......................................................................................................................17

求次优解、第 K 优解..............................................................................................................17

小结...........................................................................................................................................18

P01: 01 背包问题

题目

有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 c[i]，价值是 w[i]。

求解将哪些物品装入背包可使价值总和最大。

基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即 f[i][v]表示前 i 件物品恰放入一个容量为 v 的背包可以

获得的最大价值。则其状态转移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。

所以有必要将它详细解释一下：“将前 i 件物品放入容量为 v 的背包中”这个子问

题，若只考虑第 i 件物品的策略（放或不放），那么就可以转化为一个只牵扯

前 i-1 件物品的问题。如果不放第 i 件物品，那么问题就转化为“前 i-1 件物品放

入容量为 v 的背包中”，价值为 f[i-1][v]；如果放第 i 件物品，那么问题就转化

为“前 i-1 件物品放入剩下的容量为 v-c[i]的背包中”，此时能获得的最大价值就

是 f[i-1][v-c[i]]再加上通过放入第 i 件物品获得的价值 w[i]。

优化空间复杂度

以上方法的时间和空间复杂度均为 O(VN)，其中时间复杂度应该已经不能再优

化了，但空间复杂度却可以优化到 O。

先考虑上面讲的基本思路如何实现，肯定是有一个主循环 i=1..N，每次算出来

二维数组 f[i][0..V]的所有值。那么，如果只用一个数组 f[0..V]，能不能保证

第 i 次循环结束后 f[v]中表示的就是我们定义的状态 f[i][v]呢？f[i][v]是由 f[i-

1][v]和 f[i-1][v-c[i]]两个子问题递推而来，能否保证在推 f[i][v]时（也即在第

i 次主循环中推 f[v]时）能够得到 f[i-1][v]和 f[i-1][v-c[i]]的值呢？事实上，这

要求在每次主循环中我们以 v=V..0 的顺序推 f[v]，这样才能保证推 f[v]时 f[v-

c[i]]保存的是状态 f[i-1][v-c[i]]的值。伪代码如下：

for i=1..N

for v=V..0

f[v]=max{f[v],f[v-c[i]]+w[i]};

其中的 f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程 f[i]

[v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的 f[v-c[i]]就相当于原来的 f[i-

1][v-c[i]]。如果将 v 的循环顺序从上面的逆序改成顺序的话，那么则成了 f[i]

[v]由 f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题 P02

最

简捷的解决方案，故学习只用一维数组解 01 背包问题是十分必要的。

事实上，使用一维数组解 01 背包的程序在后面会被多次用到，所以这里抽象

出一个处理一件 01 背包中的物品过程，以后的代码中直接调用不加说明。

过程 ZeroOnePack，表示处理一件 01 背包中的物品，两个参数

cost、weight 分别表明这件物品的费用和价值。

procedure ZeroOnePack(cost,weight)

for v=V..cost

f[v]=max{f[v],f[v-cost]+weight}

注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成

v=V..0 是为了在程序中体现每个状态都按照方程求解了，避免不必要的思维复

杂度。而这里既然已经抽象成看作黑箱的过程了，就可以加入优化。费用为

cost 的物品不会影响状态 f[0..cost-1]，这是显然的。

有了这个过程以后，01 背包问题的伪代码就可以这样写：

for i=1..N

ZeroOnePack(c[i],w[i]);

初始化的细节问题

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的

题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。

一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了 f[0]为 0 其它

f[1..V]均设为-∞，这样就可以保证最终得到的 f[N]是一种恰好装满背包的最优

解。

剩余17页未读，继续阅读

评论收藏

内容反馈

pp496

粉丝: 0
资源: 4

背包问题九讲(ACM好东西)

背包问题九讲（非常不错的动态规划讲解，搞ACM必备）

ACM---背包问题大全！不用说一定不会让你失望！非常经典！非常详细！

ACM背包问题九讲

背包问题九讲

ACM背包问题九讲，算法学习

acm背包问题九解下载

背包九讲精讲acm必看

背包问题九讲2.0(13年修订版)

背包问题九讲 v1.0

杭电ACM课件2014(含背包九讲)

背包问题九讲.chm

acm背包问题讲解，c++

背包 问题 九讲

背包九讲，背包问题九讲

背包问题九讲背包九讲背包九讲

ACM背包九讲

ACM DP 背包9讲

动态规划经典--背包九讲

ACM培训资料--背包九讲

最新资源

背包问题九讲