python备忘录算法解决01背包问题

01背包问题是经典的动态规划问题，其主要思想是利用递推的方式，将问题分解为子问题来求解。

假设有n个物品，每个物品有一个重量w[i]和一个价值v[i]，现在有一个容量为C的背包，问如何选择物品能够使得背包中的总价值最大。

下面是Python代码实现：

def knapsack(C, w, v):
    n = len(w)
    # 初始化状态矩阵
    dp = [[0 for _ in range(C+1)] for _ in range(n+1)]
    # 递推计算状态矩阵
    for i in range(1, n+1):
        for j in range(1, C+1):
            if j < w[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+v[i-1])
    # 返回最优解
    return dp[n][C]

其中，状态矩阵dp[i][j]表示在前i个物品中，容量为j的背包中所能得到的最大价值。

时间复杂度为O(nC)，空间复杂度为O(nC)。

相关问题

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为背包容量。

备忘录求解背包问题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)