01背包备忘录方法python

01背包问题是一个经典的动态规划问题，备忘录方法可以用来优化其时间复杂度。以下是一个Python实现：

def knapsack01_memoization(weights, values, capacity):
    n = len(weights)
    memo = [[None] * (capacity + 1) for _ in range(n)]

    def dp(i, j):
        if i < 0 or j <= 0:
            return 0
        if memo[i][j] is not None:
            return memo[i][j]
        if j >= weights[i]:
            memo[i][j] = max(dp(i-1, j), dp(i-1, j-weights[i]) + values[i])
        else:
            memo[i][j] = dp(i-1, j)
        return memo[i][j]

    return dp(n-1, capacity)

其中，`weights`和`values`分别为物品的重量和价值，`capacity`为背包容量。`memo`是一个二维数组，用来记录状态转移过程中的中间结果。`dp(i, j)`表示在前`i`个物品中选择不超过`j`的重量所能得到的最大价值。如果`memo[i][j]`已经计算过，直接返回它的值，否则根据状态转移方程计算。

时间复杂度为$O(nC)$，其中$n$为物品数量，$C$为背包容量。