动态规划经典：《背包问题九讲》2.0alpha1详解

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

《背包问题九讲》alpha 2.0是由崔添翼（TianyiCui，网名dd_engi）在2011年9月编写的经典动态规划讲义，它作为《动态规划的思考艺术》系列的一部分，是对经典的背包问题进行深入讲解和探讨的资料。该讲义最初以HTML格式在互联网上发布，后经作者重新制作和修订，以LaTeX格式呈现，提供了2.0alpha1版本。 1. **01背包问题**：本部分介绍了经典的背包问题，涉及如何在给定容量限制下，选择物品以最大化价值。核心思路是通过动态规划，建立状态转移方程，逐步填充背包，同时考虑物品的价值和体积。空间复杂度的优化和初始化细节问题也被详细讨论，包括一个常数优化，以提高算法效率。 2. **完全背包问题**：与01背包不同，完全背包允许每个物品无限次取用。这里主要讲述了如何运用基本思路解决，一个有效优化方法是通过二分查找，将问题转化为01背包求解，以及一个O(VN)的算法。 3. **多重背包问题**：多重背包允许每种物品有多个实例。这部分首先定义了问题，接着提出基本算法，随后介绍如何将其转化为01背包形式，最后提供了一个O(VN)的解决方案。 4. **混合背包问题**：讲述了混合01背包、完全背包和多重背包的复杂情况，如何通过组合策略解决问题，并总结了这一阶段的关键点。 5. **二维费用的背包问题**：物品不仅有价值，还有对应的费用。这里介绍了解决此类问题的算法，考虑了物品总数限制和复整数域上的特殊情况。 6. **分组的背包问题**：问题扩展到物品可以分为不同的组，讨论了相应的算法和小结。 7. **有依赖的背包问题**：包含依赖关系的物品，首先简化问题，然后提出相应的算法处理更一般的情况。 8. **泛化物品**：定义了泛化物品的概念，分析了其和的计算以及在背包问题中的应用。 9. **背包问题问法变化**：涵盖了输出具体方案、字典序最小的最优方案、求解方案总数、最优方案总数，以及次优解和第K优解等问题的不同求解策略。《背包问题九讲》alpha 2.0是一份详尽且实用的教程，涵盖了多种背包问题的变体和解决方案，适合动态规划学习者深入理解和实践动态规划算法在实际问题中的应用。

中”这个子问题，若只考虑第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页未读，继续阅读

xinlinqi8

粉丝: 2
资源: 2

动态规划经典：《背包问题九讲》2.0alpha1详解

jcaptcha-2.0-alpha-1

背包九讲(tianyi cui)

TextMate2.0-alpha For Mac

使用正点原子IMX6ULL ALPHA v2.0开发板，外接DHT11温湿度传感器，温湿度监测:LINUX驱动程序开发+QT应用程序，开发板与温湿度传感器相连，在屏幕显示温湿度数据。

可以给我讲讲alphabeta剪枝的实现方法吗

ubuntu安装arduino ide2.0

alpha = 1.5 # 对比度beta = 50 # 亮度img_contrast = cv2.convertScaleAbs(img, alpha=alpha, beta=beta)

GAT tensorflow 2.0代码有图

C++实现三分之一倍频程

最新资源