python备忘录解决背包问题

背包问题是一类经典的动态规划问题，可以用备忘录方法来解决。以下是一个Python实现的备忘录解决背包问题的代码：

def knapsack(values, weights, capacity):
    n = len(values)
    memo = [[None] * (capacity + 1) for _ in range(n + 1)]
    
    def dp(i, j):
        if memo[i][j] is not None:
            return memo[i][j]
        if i == 0 or j == 0:
            result = 0
        elif weights[i-1] > j:
            result = dp(i-1, j)
        else:
            result = max(dp(i-1, j), dp(i-1, j-weights[i-1]) + values[i-1])
        memo[i][j] = result
        return result
    
    return dp(n, capacity)

该函数的参数为物品价值列表values、物品重量列表weights和背包容量capacity。它返回能够放进背包的最大价值。

函数内部使用了一个记忆化数组memo，其中memo[i][j]表示在前i个物品中选择，在容量为j的背包中能够获得的最大价值。当memo[i][j]不为空时，直接返回memo[i][j]；否则，如果i为0或j为0，则返回0；如果第i个物品重量超过了背包容量j，则只能不选第i个物品，返回dp(i-1, j)；否则，可以选择或不选第i个物品，分别计算放入和不放入时的最大价值，取较大值。最后将结果保存在memo[i][j]中并返回。

该算法的时间复杂度为O(n * C)，其中n为物品数量，C为背包容量。