备忘录方法求解01背包

01背包问题是一个经典的动态规划问题，可以使用备忘录方法（即记忆化搜索）来求解。

具体步骤如下：

1. 定义备忘录数组memo，其中memo[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。

2. 初始化，将memo数组中所有元素初始化为-1，表示该状态还未被搜索过。

3. 递归搜索。对于每个状态memo[i][j]，如果其值为-1，则进行递归搜索。如果第i个物品的重量大于j，则不能选取该物品，此时memo[i][j] = memo[i-1][j]。如果第i个物品的重量小于等于j，则可以选择该物品，此时memo[i][j] = max(memo[i-1][j], memo[i-1][j-w[i]] + v[i])，其中w[i]和v[i]分别表示第i个物品的重量和价值，max表示取两者中的最大值。

4. 返回memo[n][m]，即前n个物品放入容量为m的背包中所能获得的最大价值。

代码实现如下：

def knapsack(w, v, m):
    n = len(w)
    memo = [[-1] * (m + 1) for _ in range(n + 1)]
    def helper(i, j):
        if memo[i][j] != -1:
            return memo[i][j]
        if i == 0 or j == 0:
            memo[i][j] = 0
        elif w[i-1] > j:
            memo[i][j] = helper(i-1, j)
        else:
            memo[i][j] = max(helper(i-1, j), helper(i-1, j-w[i-1]) + v[i-1])
        return memo[i][j]
    return helper(n, m)

# 示例：
w = [2, 1, 3, 2]
v = [12, 10, 20, 15]
m = 5
print(knapsack(w, v, m))  # 输出：37