使用动态规划解决背包问题

Question

我在实现一个背包问题的代码，使用的是我在这个链接找到的算法：背包问题

我这里也附上了这个算法的代码片段。

我写了以下的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 查看结果