作为课程的一部分，我一直在学习动态编程，并为背包0-1问题的DP解决方案奋斗了几天。我对问题和解决方案的理解是：
我们有物品(A, B, C, D)，一个最大保持重量W = 10的背包，每个物品的重量/值是A = 2w/1v, 2w/3v, 5w/8v, 6w,5v。
该解决方案要求我们研究子问题，其中我们将背包重量限制在0->W和来自A->D.
我不明白的是
- 如何直观地得出这个解决方案
- 为什么即使项目的顺序不同，解决方案也能工作，因为我们需要迭代每个项目
- 如果在没有DP的情况下使用暴力尝试所有组合的方法，那么DP子问题解决方案如何解释背包解决方案的所有可能组合
-
不知道你说的"直观地"；但我们可以理解如何形成递推关系，并将其应用于问题参数。
-
由于每个子问题都与当前项目和我们已经访问过的子问题相关，因此无论顺序如何，搜索都能工作。复发确实说明了"；所有组合"；；这就是为什么如果我们访问A->B、 当我们到达C时，我们本质上是在尝试A B AB C AC BC和ABC；如果我们宁愿访问A->C、 则B；我们会得到相同的整体可能性，假设加法是关联的(A C AC B BA BC BAC(。(我们实际上并没有访问所有组合，请参阅3。(
-
我们通过一般访问W*N的整个搜索空间来说明所有可能性。由于我们受W的约束，所有权重和组合都将降到或低于W，DP所做的是记录每个可实现权重的最佳可见值。当我们到达第
i个项目时，我们不需要知道创建所有总和的项目的具体组合(我们可能想追溯实际项目，但这不需要详尽的记录(。对于我们迭代的每个权重(每次访问一个项目时，我们迭代所有可能的权重(，我们只需要知道(1(在相同权重下看到的最佳值(因此不使用该项目(，以及(2(在比该项目的权重低的权重处看到的最佳值(如果我们使用该项目，则我们希望将其值添加到在该较低权重处看到到的最佳值，因此这两个权重一起表示我们在权重迭代中所处的当前权重(。对于dp[i][w]处的值，我们选择(1(和(2(中的最佳值。