动态规划解析：背包问题九讲2.0

需积分: 0 187 浏览量更新于2024-07-25 收藏 236KB PDF 举报

"《背包九讲》是崔添翼（TianyiCui，a.k.a.dd_engi）创作的一篇关于动态规划在背包问题中的应用教程，属于《动态规划的思考艺术》系列的更新版，最初以HTML形式发布，后经修订以LaTeX制作成2.0alpha1版本，并在GitHub上提供修订历史和最新版本。该教程采用CC BY-NC-SA协议进行发布。" 《背包九讲》涵盖了多种类型的背包问题，包括： 1. **01背包问题**：这是一种经典的动态规划问题，要求在不超过背包容量的前提下，选择物品以最大化价值。基础思路是通过状态转移方程建立二维数组，优化空间复杂度时可以使用滚动数组。初始化细节和常数优化也是关键。 2. **完全背包问题**：与01背包不同，每个物品可以无限件。可以通过将问题转化为01背包问题来解决，或者直接设计O(VN)的时间复杂度算法。 3. **多重背包问题**：每个物品有限定的数量，需要考虑物品数量限制。可以转化为01背包问题或直接使用O(VN)的算法。 4. **混合三种背包问题**：结合01、完全和多重背包的特点，需要灵活处理不同背包类型的组合。 5. **二维费用的背包问题**：除了考虑价值，物品还有费用，目标是在不超过预算的情况下最大化价值。可以扩展到考虑物品总个数限制，甚至复整数域上的情况。 6. **分组的背包问题**：物品被分成多个组，每组有自己的容量限制，需要在组内选择物品以最大化组价值。 7. **有依赖的背包问题**：某些物品的选取可能依赖于其他物品，算法需要处理这种依赖关系。 8. **泛化物品**：引入了更复杂的物品类型，如物品可以是其他物品的组合，需要扩展背包问题的解决方案以适应这些情况。 9. **背包问题问法的变化**：除了求解最优价值，还可能要求输出方案、字典序最小的最优方案、方案总数，甚至是次优解和第K优解。此教程详细介绍了每种问题的基本思路、优化方法和小结，对于学习和理解动态规划以及背包问题的应用提供了深入的指导。通过阅读和实践，读者能够掌握如何运用动态规划解决实际的背包问题。

中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化

为一个只和前i − 1件物品相关的问题。如果不放第i件物品，那么问题就转化

为“前i − 1件物品放入容量为v的背包中”，价值为F [i − 1, v]；如果放第i件物

品，那么问题就转化为“前i − 1件物品放入剩下的容量为v − C

的背包中”，

此时能获得的最大价值就是F [i − 1, v − C

]再加上通过放入第i件物品获得的价

值W

。

伪代码如下：

F [0, 0..V ] = 0

for i = 1 to N

for v = C

to V

F [i, v] = max{F [i − 1, v], F [i − 1, v − C

] + W

}

1.3 优化空间复杂度

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

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

先考虑上面讲的基本思路如何实现，肯定是有一个主循环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

]两个子问题递推而来，能否保证在推F [i, v]时（也

即在第i次主循环中推F [v]时）能够取用F [i − 1, v] 和F [i − 1, v − C

]的值呢？事

实上，这要求在每次主循环中我们以v = V..0的递减顺序计算F [v]，这样才能保

证推F [v]时F [v − C

]保存的是状态F [i − 1, v − C

的值。伪代码如下：

F [0..V ] = 0

for i = 1 to N

for v = V to C

F [v] = max{F [v], F [v − C

] + W

}

其中的F [v ] = max{F [v], F [v − C

] + W

}一句，恰就对应于我们原来的转移方

程，因为现在的F [v − C

]就相当于原来的F [i − 1, v − C

]。如果将v的循环顺序

从上面的逆序改成顺序的话，那么则成了F [i, v]由F [i, v − C

]推导得到，与本题

意不符。

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

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

def ZeroOnePack(F , C, W )

for v = V to C

F [v] = max(F [v], f [v − C] + W )

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

for i = 1 to N

ZeroOnePack(F, C

, W

)

1.4 初始化的细节问题

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

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

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

剩余14页未读，继续阅读

飘渺守护者

粉丝: 0
资源: 1

动态规划解析：背包问题九讲2.0

背包九讲算法及实现.pdf

背包九讲完整版.pdf

背包九讲完整详解.pdf

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

背包九讲完整版_背包九讲

背包九讲，背包问题九讲

背包九讲问题

背包九讲算法

ACM背包九讲

背包九讲1

最新资源