背包问题备忘录解python

背包问题是动态规划中比较经典的问题，以下是备忘录解的 Python 代码：

def knapsack(W, wt, val, n):
    memo = [[None for j in range(W + 1)] for i in range(n + 1)]

    # base case
    for i in range(n + 1):
        for j in range(W + 1):
            if i == 0 or j == 0:
                memo[i][j] = 0

    # memoization
    def dp(i, j):
        if memo[i][j] is not None:
            return memo[i][j]
        if j < wt[i - 1]:
            memo[i][j] = dp(i - 1, j)
        else:
            memo[i][j] = max(dp(i - 1, j), dp(i - 1, j - wt[i - 1]) + val[i - 1])
        return memo[i][j]

    return dp(n, W)

其中，`W` 是背包的容量，`wt` 是每个物品的重量，`val` 是每个物品的价值，`n` 是物品的数量。`memo` 是备忘录，用来记录已经计算过的状态。在递归时，如果某个状态已经计算过，就直接返回备忘录中的结果。否则，按照动态规划的思路计算当前状态，并将结果存入备忘录中。最终返回 `dp(n, W)`，即所有物品放入背包中可以获得的最大价值。