c++ - 无界背包与经典背包比较

Question

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

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

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

标签： c++algorithmdynamic-programming

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