python - 使用动态规划求解背包

Question

我正在使用我在此链接 Knapsack Problem 中找到的算法来实现背包问题的片段

我也在这里附上了算法的片段。

我已经为该算法编写了以下 python 代码段。在这里:

def knapsack(v,w,n,W):
    V = [[None for x in range(W+1)] for x in range(len(v)+1)]

    for wy in range(W+1):
        V[0][wy] = 0

    for i in range(1,n+1):
        for wx in range(W+1):
            # print i,wx
            if w[i] <= wx:

                V[i][wx] = max(V[i-1][wx], v[i]+V[i-1][wx-w[i]])
            else:
                V[i][wx] = V[i-1][wx]
    return V[n][W]

print knapsack(v = [10,40,30,50],w=[5,4,6,3],n=4,W=10)

我应该在 [4,9] 位置得到输出 90 。我在这里做错了什么？

Answer 1

我不确定，但我认为错误是

• 元素 v 和 w 是从 0 开始的索引(0 到 n-1)
• 您正在 1 到 n 范围内迭代
• 因此 w[n] 或 v[n] 将抛出 IndexError

更新代码:

def knapsack(v,w,n,W):
    V = [[None for x in range(W+1)] for x in range(len(v)+1)]

    for wy in range(W+1):
        V[0][wy] = 0

    for i in range(1,n+1):
        for wx in range(W+1):
            # print i,wx
            if w[i-1] <= wx:

                V[i][wx] = max(V[i-1][wx], v[i-1]+V[i-1][wx-w[i-1]])
            else:
                V[i][wx] = V[i-1][wx]
    return V[n][W]

print knapsack(v = [10,40,30,50],w=[5,4,6,3],n=4,W=10)

现在输出为 90。

在 Ideone 查看结果