python01背包问题备忘录

背包问题是一个经典的动态规划问题，其主要思想是将问题拆分成子问题，通过计算子问题的最优解，来推导出原问题的最优解。

以下是 Python 实现 0-1 背包问题的备忘录：

def knapsack(W, wt, val, n, memo):
    if n == 0 or W == 0:
        return 0
    if memo[n][W] != -1:
        return memo[n][W]
    if wt[n-1] > W:
        memo[n][W] = knapsack(W, wt, val, n-1, memo)
        return memo[n][W]
    else:
        memo[n][W] = max(val[n-1]+knapsack(W-wt[n-1], wt, val, n-1, memo), knapsack(W, wt, val, n-1, memo))
        return memo[n][W]

W = 50
wt = [10, 20, 30]
val = [60, 100, 120]
n = len(val)
memo = [[-1 for i in range(W+1)] for j in range(n+1)]
print(knapsack(W, wt, val, n, memo))

其中，`W` 表示背包的最大容量，`wt` 表示物品的重量列表，`val` 表示物品的价值列表，`n` 表示物品的数量。`memo` 列表用于存储已经求解过的子问题的最优解，避免重复计算。