两种写法算得一样吗
二维写法取 dp[3][10],一维写法取 dp[10]。运行下面这段程序:
def knap2d(items, cap):
dp = [[0] * (cap + 1) for _ in range(len(items) + 1)]
for i in range(1, len(items) + 1):
w, v = items[i - 1]
for c in range(cap + 1):
dp[i][c] = dp[i - 1][c]
if c >= w and dp[i - 1][c - w] + v > dp[i][c]:
dp[i][c] = dp[i - 1][c - w] + v
return dp
def knap1d(items, cap):
dp = [0] * (cap + 1)
for w, v in items:
for c in range(cap, w - 1, -1):
if dp[c - w] + v > dp[c]:
dp[c] = dp[c - w] + v
return dp
print(str(knap2d([(3, 8), (4, 9), (5, 11)], 10)[3][10]) + "/" + str(knap1d([(3, 8), (4, 9), (5, 11)], 10)[10]))
全部评论