algorithm - 背包 0-1 动态规划解决方案背后的直觉？

Question

作为课程的一部分，我一直在学习动态编程，并且几天来一直在努力解决背包 0-1 问题的 DP 解决方案。我对问题和解决方案的理解是这样的：

我们有 items (A, B, C, D)，一个W = 10最大重量的背包，每个项目的重量/值是A = 2w/1v, 2w/3v, 5w/8v, 6w,5v。

该解决方案要求我们查看将背包重量限制在 0 -> W 以及从 A -> D 限制项目的子问题。

我不明白的是

1. 如何直观地得出这个解决方案？
2. 既然我们需要遍历每个项目，为什么即使项目的顺序不同，解决方案也能工作？
3. 如果一个人在没有 DP 的情况下这样做并使用蛮力尝试所有组合方法，那么 DP 子问题解决方案如何解释所有可能的背包解决方案组合？

标签： algorithmdynamic-programming

Answer 1

1. 不确定您所说的“直观”是什么意思，但我们可以了解如何形成递归关系并将其应用于问题参数。

2. 该解决方案无论顺序如何都有效，因为每个子问题都与当前项目和我们已经访问过的子问题相关。重复确实考虑了“所有组合”；这就是为什么如果我们访问 A -> B，当我们到达 C 时，我们实际上是在尝试 AB AB C AC BC 和 ABC；如果我们宁愿访问 A -> C，那么 B；考虑到加法是关联的（AC AC B BA BC BAC），我们会得到相同的整体可能性。（我们实际上并没有访问所有组合，请参见 3。）

3. 我们通过访问 W*N 的整个搜索空间来考虑所有可能性。由于我们受 W 约束，所有权重总和组合将落在或低于它，DP 所做的是记录每个可实现权重的最佳可见值。当我们到达i第一项，我们不需要知道创建所有总和的项的具体组合（我们可能想追溯实际项，但这不需要详尽的记录）。对于我们迭代的每个权重（我们每次访问一个项目时迭代所有可能的权重），我们只需要知道（1）在相同权重下看到的最佳值（所以不使用这个项目），以及（2）在比这个项目的重量更低的重量下看到的最佳值（如果我们正在使用这个项目，那么我们希望将它的值添加到在该较低重量下看到的最佳值，这样两个重量一起代表我们在重量中的当前重量迭代）。我们为 处的值选择 (1) 和 (2) 中的最佳值dp[i][w]。