動的計画法

dynamic_programming.py

from functools import cache


def knapsack(weights, values, capacity):
    """0/1 knapsack: best total value within capacity (bottom-up, one row)."""
    best = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):  # high to low: each item used at most once
            best[c] = max(best[c], best[c - w] + v)
    return best[capacity]


def lcs(a, b):
    """Length of the longest common subsequence (top-down, memoized)."""
    @cache
    def solve(i, j):
        if i == len(a) or j == len(b):
            return 0
        if a[i] == b[j]:
            return 1 + solve(i + 1, j + 1)
        return max(solve(i + 1, j), solve(i, j + 1))

    return solve(0, 0)


print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))  # 9
print(lcs("ABCBDAB", "BDCABA"))                # 4

python dynamic_programming.py