为什么在无界背包的情况下构造一维数组而在 0/1 背包的情况下构造二维数组？
Why is there a 1-D array constructed in case of unbounded knapsack and 2-D array constructed in case of 0/1 knapsack?
我看到在无界背包的情况下构造一维数组，在0/1背包的情况下构造二维数组？为什么会这样？这个问题是参考动态规划问的。
动态编程通过维护 "states" 来工作，当然您希望使用最少的变量来表示状态。
现在，这两个问题的不同之处在于，在 Unbounded knapsack problem 中，您可以多次选择单个物品，而在 0-1 knapsack problem 中，您只能选择一次物品。这意味着，我想在 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 并获得权重为 w - wt[i] 的项目 i-1 的最佳解决方案，这确保我们不会多次选择项目 i。
查看无界背包DP：dp[w] = max(dp[w], dp[w - wt[i] ] + val[i] )。不需要记住我们之前是否选择过 ith 项，如果它给我们带来最大值，我们可以重复使用它。
我看到在无界背包的情况下构造一维数组，在0/1背包的情况下构造二维数组？为什么会这样？这个问题是参考动态规划问的。
动态编程通过维护 "states" 来工作，当然您希望使用最少的变量来表示状态。
现在，这两个问题的不同之处在于，在 Unbounded knapsack problem 中，您可以多次选择单个物品，而在 0-1 knapsack problem 中，您只能选择一次物品。这意味着，我想在 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 并获得权重为 w - wt[i] 的项目 i-1 的最佳解决方案，这确保我们不会多次选择项目 i。
查看无界背包DP：dp[w] = max(dp[w], dp[w - wt[i] ] + val[i] )。不需要记住我们之前是否选择过 ith 项，如果它给我们带来最大值，我们可以重复使用它。