五项一起对得上吗

👁️ 0 人浏览 💬 0 人评论 ❤️ 添加收藏

运行下面这段程序:

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)
提交你的答案
请登录后提交答案。
去登录
代码编辑器
Ctrl + Enter 运行
本次输入:
输出:

                        
👩‍🏫
AI
💬 题目评论

全部评论