代码之家 › 专栏 › 技术社区 › deficiencyOn

用DP求解“背包”

np computer-science algorithm python

0

deficiencyOn · 技术社区 · 6 年前

这是我的代码:

def knapsack_dynamic(ws, vs, W):
    n = len(ws)
    K = [[0] * (W+1)] * (n+1)

    for i in range(n+1):
        for w in range(W+1):

            if i  == 0 or w == 0: # knapsack is empty or no more weight to carry
                K[i][w] = 0
            else:
                if ws[i-1] > w:
                    K[i][w] = K[i-1][w]
                else:
                    K[i][w] = max(vs[i-1] + K[i-1][w-ws[i-1]], K[i-1][w])
    return K[n][W]

下面是测试方法:

maxw = 50
ws = [10, 20, 30]
vs = [60, 100, 120]
print(knapsack_dynamic(ws, vs, maxw)) # should print 220

我不知道为什么我会 300 而不是 220 。

你能帮我弄清楚吗?

1 回复 | 直到 6 年前

1

sciroccorics 6 年前

矩阵初始化期间出错:

代替

K = [[0] * (W+1)] * (n+1)

通过

K = [[0] * (W+1) for i in range(n+1)]

或由

K = [[0 for w in range(W+1)] for i in range(n+1)]

应用repeat运算符时 * 在嵌套列表上,仅重复引用,而不重复值。

尝试以下简单示例:

m = [[0] * 4] * 3
print(m) # --> [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
m[0][0] = 5
print(m) # --> [[5, 0, 0, 0], [5, 0, 0, 0], [5, 0, 0, 0]]

推荐文章

svaerth · 使用巨型哈希表在多项式时间内求解数独

6 年前

Tamar Geldiashvili · 如何检查一行的数据是否在np内部的列表中。where()?

6 年前

user3535074 · Pandas系列不区分大小写的匹配和值之间的部分匹配

7 年前

little_monster · 每种语言都属于P还是NP?

10 年前