### 01背包问题的Python实现及解析 #### 背景介绍 01背包问题是经典的动态规划问题之一，其核心在于如何通过有限的资源（如背包容量），最大化目标函数（如物品的价值）。该问题的特点是每种物品仅能选择一次。 #### Python代码实现 以下是基于动态规划方法解决01背包问题的标准Python实现： ```python def knapsack_01(values, weights, capacity): """ 解决01背包问题 参数: values (list[int]): 各物品的价值 weights (list[int]): 各物品的重量 capacity (int): 背包的最大承重 返回: int: 最大可获得的价值 """ n = len(values) # 物品数量 dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)] # 创建二维DP表 # 填充DP表 for i in range(1, n + 1): for j in range(1, capacity + 1): if weights[i - 1] <= j: # 当前物品可以放入背包 dp[i][j] = max( values[i - 1] + dp[i - 1][j - weights[i - 1]], # 放入当前物品 dp[i - 1][j] # 不放入当前物品 ) else: dp[i][j] = dp[i - 1][j] # 当前物品无法放入背包 return dp[n][capacity] # 测试数据 values = [60, 100, 120] # 各物品的价值 weights = [10, 20, 30] # 各物品的重量 capacity = 50 # 背包的最大承重 max_value = knapsack_01(values, weights, capacity) print(f"最大价值为: {max_value}") ``` --- #### 代码解析过程 ##### 1. **定义状态** 设 `dp[i][j]` 表示从前 `i` 件物品中选取若干件放进容量为 `j` 的背包所能获取的最大价值。其中： - `i` 是考虑的物品编号； - `j` 是当前背包剩余容量。 ##### 2. **状态转移方程** 对于第 `i` 件物品，有两种可能的选择： - **不选此物品**：此时背包内的最大价值保持不变，即 `dp[i][j] = dp[i-1][j]`。 - **选此物品**：前提是当前物品的重量不超过背包容量 (`weights[i-1] <= j`)，则更新最大价值为 `dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i-1][j-weights[i-1]])`[^1]。 ##### 3. **初始化条件** 为了简化边界处理，通常将 `dp[0][*]` 和 `dp[*][0]` 初始化为零，表示没有任何物品或者背包容量为零时，最大价值均为零。 ##### 4. **返回结果** 最终的结果存储在 `dp[n][capacity]` 中，代表从所有物品中选出最优组合后的最大价值。 --- #### 进一步优化空间复杂度 由于每次计算只依赖于上一层的状态，因此可以通过一维数组代替二维数组来降低空间复杂度： ```python def optimized_knapsack_01(values, weights, capacity): """ 使用滚动数组优化的空间复杂度版本 """ n = len(values) dp = [0] * (capacity + 1) for i in range(1, n + 1): for j in range(capacity, weights[i - 1] - 1, -1): dp[j] = max(dp[j], values[i - 1] + dp[j - weights[i - 1]]) return dp[capacity] ``` 这种优化方式的核心是从后向前迭代背包容量，从而避免覆盖未使用的旧值[^2]。 --- #### 多次采药的情况扩展 当允许重复采集某种物品时，问题变为完全背包问题。在这种情况下，只需调整内部循环方向即可： ```python def complete_knapsack(values, weights, capacity): """ 完全背包问题解法 """ n = len(values) dp = [0] * (capacity + 1) for i in range(1, n + 1): for j in range(weights[i - 1], capacity + 1): dp[j] = max(dp[j], values[i - 1] + dp[j - weights[i - 1]]) return dp[capacity] ``` 这里的关键区别在于内层循环从小到大遍历背包容量，使得同一件物品能够被多次加入背包[^3]。 --- ###