无界背包与古典背包比较

Question

我在网上读到了两个截然不同的问题0-1 背包问题 和无界背包问题。我发现这两个问题都可以通过动态规划来解决，但是有两种不同的方式。如果0-1背包问题使用二维数组解决，无界背包问题仅使用一维数组。

你可以阅读更多0-1 Knapsack Problem and Unbounded Knapsak Problem

这两个问题的区别，据我所知，0-1背包问题只包含有限数量的东西，而无界背包Problem 允许获取任何资源的 1 个或多个实例。但是，我不知道为什么要改变解决这个问题的方法？你能告诉我这是什么原因吗？

Answer 1

Table 方法更容易解释和调试，这就是为什么算法描述通常这样显示。

请注意，对于 0-1 背包问题，我们必须排除重复使用物品两次的可能性。因此，在外循环的每一步，我们都会使用当前项目更新之前的最佳结果。

但我们只使用 table 的最后一行（查看索引 i 和 i-1），因此我们可以将 table 大小减小到 2 x Capacity 仅使用当前行和最后一行。

此外，我们可以使用一维数组的方法，应用一个技巧——为了避免重复使用item，我们可以进行反向遍历。

Python 下面的代码使用来自 wiki 页面的数据并显示 table 和线性数组实现。

wt = [23,26,20,18,32,27,29,26,30,27]
val = [505,352,458,220,354,414,498,545,473,543]

def knap1(w,v, cap):
    n = len(w)
    m = [[0]*(cap+1) for _ in range(n)]
    for i in range(n):
        for j in range(cap + 1):
            if w[i] > j:
                m[i][j] = m[i-1][j]
            else:
                m[i][j] = max(m[i-1][j], m[i-1][j-w[i]] + v[i])
    return m[n-1][cap]

def knap2(w,v, cap):
    n = len(w)
    m = [0]*(cap+1)
    for i in range(n):
        for j in range(cap, w[i]-1,-1):
                m[j] = max(m[j], m[j-w[i]] + v[i])
    return m[cap]


print(knap1(wt, val, 67))
print(knap2(wt, val, 67))

>>1270
>>1270

无界背包与古典背包比较

Unbounded Knapsack and Classical Knapsack Comparison

c++

algorithm

dynamic-programming