### Python 实现 0-1 背包问题 以下是基于动态规划方法实现的 Python 程序来解决给定体积和价值列表的 0-1 背包问题： #### 动态规划核心思路 定义二维数组 `dp`，其中 `dp[i][j]` 表示从前 `i` 个物品中选择若干个放入容量为 `j` 的背包所能得到的最大价值。对于每个物品有两种情况： 1. **不选当前物品**：则最大价值等于 `dp[i-1][j]`。 2. **选当前物品**：前提是背包剩余容量允许，则最大价值等于 `dp[i-1][j-weight[i]] + value[i]`。 综合上述两种情况取较大者作为结果[^3]。 #### 完整代码实现 ```python def knapsack_01(values, weights, capacity): n = len(values) # 创建 dp 数组并初始化为 0 dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)] # 填充 dp 数组 for i in range(1, n + 1): for j in range(capacity + 1): if weights[i - 1] <= j: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]) else: dp[i][j] = dp[i - 1][j] # 找到具体选择了哪些物品 selected_items = [] w = capacity for i in range(n, 0, -1): if dp[i][w] != dp[i - 1][w]: selected_items.append(i - 1) # 物品编号从 0 开始计数 w -= weights[i - 1] return dp[n][capacity], list(reversed(selected_items)) # 测试数据 values = [60, 100, 120] # 各物品的价值 weights = [10, 20, 30] # 各物品的重量 capacity = 50 # 背包容积 # 计算结果 max_value, items_selected = knapsack_01(values, weights, capacity) print(f'最大价值为: {max_value}') print('选择的物品索引为:', items_selected) ``` #### 输出解释 运行以上程序会输出如下内容： ``` 最大价值为: 220 选择的物品索引为: [1, 2] ``` 这表明在给定条件下，选取第二个和第三个物品可以获得总价值最大的方案。 --- ### 关键点解析 1. **状态转移方程** 动态规划的核心是构建状态转移方程。这里的状态转移方程为： \[ dp[i][j] = \begin{cases} \text{max}(dp[i-1][j], dp[i-1][j-\text{weight}[i]]+\text{value}[i]), & \text{if } j \geq \text{weight}[i]\\ dp[i-1][j], & \text{otherwise}. \end{cases} \] 这一公式描述了是否选择第 \(i\) 个物品的情况下的最优解[^5]。 2. **回溯路径** 使用双重循环填充 DP 表格后，通过反向追踪找到具体的物品组合。此过程依赖于比较当前单元格与其上方单元格的值差异，从而判断某物品是否被选用[^2]。 ---