无界背包与经典背包对比

Question

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

您可以阅读更多0-1背包问题和无界背包问题

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

Answer 1

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

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

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

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

下面的 Python 代码使用 wiki 页面中的数据并显示了表和线性数组的实现。

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