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

01背包问题备忘录算法伪代码

### 01背包问题的备忘录算法伪代码

对于01背包问题，采用动态规划中的备忘录方法能够有效减少重复计算，提高效率。这种方法通过记录已经解决过的子问题的结果来避免不必要的重新计算。

#### 初始化阶段
创建一个二维数组 `memo` 来存储中间结果，其大小为 `(N+1)×(V+1)`，其中 `N` 表示物品数量，而 `V` 是指背包的最大容量。初始化时将所有元素设置为空值或特定标记表示尚未访问过该位置的状态[^3]。

def knapsack_memo(N, V, weights, values):
    memo = [[None]*(V + 1) for _ in range(N + 1)]
    
    def dp(n, v):
        if n == 0 or v == 0:
            return 0
        
        if memo[n][v] is not None:
            return memo[n][v]

        weight_n = weights[n - 1]
        value_n = values[n - 1]

        res = dp(n - 1, v)

        if weight_n <= v:
            res = max(res, dp(n - 1, v - weight_n) + value_n)
        
        memo[n][v] = res
        return res
    
    result = dp(N, V)
    return result

在这个函数中：

- 参数 `weights[]` 和 `values[]` 分别保存每件商品的质量和价值；
- 函数内部定义了一个辅助函数 `dp()`，用于递归求解最优解并利用 `memo[][]` 数组缓存已知的最佳选择方案；当遇到相同参数调用时可以直接返回之前储存的答案而不是再次执行完整的逻辑流程[^2]。

此段代码实现了基于记忆化的自顶向下方式解决问题，在每次尝试放入新物件前先查询表内是否存在对应情形下的最大收益，如果存在则直接取回而不必继续深入探讨其他可能性，从而大大降低了时间复杂度。