备忘录求解背包问题python

以下是一个用 Python 解决背包问题的备忘录算法实现。假设有一个物品列表 `items` 和对应的价值列表 `values`，以及背包的容量 `capacity`。

def knapsack_memo(items, values, capacity):
    n = len(items)
    memo = [[-1 for _ in range(capacity + 1)] for _ in range(n + 1)]
    # 将所有的初始值设为 -1

    def dp(i, j):
        if memo[i][j] != -1:
            return memo[i][j]

        if i == 0 or j == 0:
            res = 0
        elif items[i - 1] > j:
            res = dp(i - 1, j)
        else:
            res = max(dp(i - 1, j), dp(i - 1, j - items[i - 1]) + values[i - 1])

        memo[i][j] = res
        return res

    return dp(n, capacity)

在上面的代码中，我们定义了一个 `memo` 数组，用于保存子问题的最优解。在递归函数 `dp` 中，我们先检查 `memo[i][j]` 是否已经计算过，如果是，则直接返回它的值。如果没有计算过，则按照背包问题的递推公式计算它的最优解，并将结果存入 `memo[i][j]` 中。

最后，我们调用 `dp(n, capacity)` 来计算问题的最优解。因为 `dp` 函数的参数是从 1 开始的，所以在计算时需要将 `items` 和 `values` 中的下标减 1。

示例使用：

items = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
result = knapsack_memo(items, values, capacity)
print(result)  # 输出 11

参考文献：

- [背包问题（Python实现）](https://blog.csdn.net/qq_36186690/article/details/81227809)