我发现在无限背包问题中会构造一个一维数组，而在0/1背包问题中会构造一个二维数组。为什么会这样呢？这个问题是关于动态规划的。
1个回答
2
动态规划通过维护“状态”来工作，当然您希望使用最少的变量表示状态。
现在，这两个问题的区别在于，在无界背包问题中，您可以随意选择单个物品，而在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])。没有必要记住我们是否之前选择过第i个物品，如果它给我们带来最大的价值，我们可以直接重复使用它。
- H S
2
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
这意味着，在0-1背包问题中，我想要包括我是否已经从列表中选择了一个项目，但在0-1背包问题中没有必要这样做。.. 我认为你的意思是：但在无界背包问题中不需要这样做。``` - MrSham