dynamic-programming - 为什么有无界背包构造的一维数组和0/1背包构造的二维数组？

Question

我看到在无界背包的情况下构造一维数组，在0/1背包的情况下构造二维数组？为什么会发生这种情况？这个问题是在引用动态规划时提出的。

Answer 1

动态编程通过维护“状态”来工作，当然您希望使用最少的变量来表示状态。

现在，这两个问题的不同之处在于，您可以在无界背包问题中多次选择单个项目，但是，在 0-1 背包问题中，您只能选择一个项目。这意味着，我想包括我是否已经从 0-1 背包问题中的列表中选择了一个项目，但在 0-1 背包问题中不需要这样做。这正是 0-1 背包问题中二维的原因。

参见，0-1 背包的 DP:dp[i][w] = max(val[i] + dp[i-1][w-wt[i]], K[i-1][w]); .这代表任一选择项目 i并获得项目的最佳解决方案 i-1带重量 w - wt[i] ，这确保我们不会多次选择项目 i。

见无界背包的DP:dp[w] = max(dp[w], dp[w - wt[i] ] + val[i] ) .无需记住我们是否选择了ith item 之前，我们可以重用它，如果它给了我们最大的值(value)。