五项一起对得上吗
运行下面这段程序:
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
def knap_full(items, cap):
dp = [0] * (cap + 1)
for w, v in items:
for c in range(w, cap + 1):
if dp[c - w] + v > dp[c]:
dp[c] = dp[c - w] + v
return dp
def merge_cost(a):
n = len(a)
INF = 10 ** 9
pre = [0] * (n + 1)
for i in range(n):
pre[i + 1] = pre[i] + a[i]
dp = [[0] * n for _ in range(n)]
for L in range(2, n + 1):
for i in range(n - L + 1):
j = i + L - 1
dp[i][j] = INF
for k in range(i, j):
t = dp[i][k] + dp[k + 1][j] + pre[j + 1] - pre[i]
if t < dp[i][j]:
dp[i][j] = t
return dp[0][n - 1]
def paths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
def edit(a, b):
m = len(a)
n = len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j - 1],
dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
ok = (knap1d([(3, 8), (4, 9), (5, 11)], 10)[10] == 20
and knap_full([(3, 8), (4, 9), (5, 11)], 10)[10] == 25
and merge_cost([4, 1, 2, 3]) == 19
and paths(3, 4) == 10
and edit("horse", "ros") == 3)
print(ok)
全部评论