### Python 实现动态规划解决 0-1 背包问题 以下是基于动态规划方法实现的 Python 程序，用于解决给定物品价值 `[5,4,6,2]` 和重量 `[2,4,5,3]` 的情况下，背包容量为 `8` 的最优解。 #### 动态规划核心思路 通过构建二维数组 `f[i][j]` 来记录前 `i` 个物品在背包容量为 `j` 时的最大价值。对于每个物品有两种状态：放入或不放入背包。如果放入，则需考虑剩余空间的价值；如果不放入，则保留之前的状态[^3]。 ```python def knapsack(values, weights, capacity): n = len(values) # 初始化 DP 数组 dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)] # 填充 DP 表格 for i in range(1, n + 1): wi, vi = weights[i - 1], values[i - 1] for c in range(1, capacity + 1): if c >= wi: dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wi] + vi) else: dp[i][c] = dp[i - 1][c] # 返回最大价值 return dp[n][capacity] # 输入数据 values = [5, 4, 6, 2] # 物品价值 weights = [2, 4, 5, 3] # 物品重量 capacity = 8 # 背包容量 max_value = knapsack(values, weights, capacity) print(f"背包最大价值为: {max_value}") ``` #### 输出结果解释 运行以上代码后会输出背包能够容纳的最大价值。此程序的核心在于利用动态规划逐步计算不同状态下背包能装载的最大价值，并最终返回全局最优解[^3]。 --- #### 进一步分析已选物品 为了进一步展示哪些具体物品被选入背包，可以扩展上述函数来追踪路径： ```python def trace_items(values, weights, capacity): n = len(values) dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)] # 构建DP表 for i in range(1, n + 1): wi, vi = weights[i - 1], values[i - 1] for c in range(1, capacity + 1): if c >= wi: dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wi] + vi) else: dp[i][c] = dp[i - 1][c] # 回溯找到具体的物品组合 selected = [] c = capacity for i in range(n, 0, -1): if dp[i][c] != dp[i - 1][c]: selected.append(i - 1) # 记录下标从0开始的物品编号 c -= weights[i - 1] return dp[n][capacity], selected[::-1] # 反转顺序以便按原输入顺序显示 # 使用trace_items获取最大价值以及对应的物品索引 max_val, item_indices = trace_items(values, weights, capacity) print(f"背包最大价值为: {max_val}") print("所选物品为:", ", ".join(str(idx + 1) for idx in item_indices)) ``` 在此版本中，不仅得到了最大价值，还列出了实际选取的物品编号（注意这里是从 `1` 开始计数）。这有助于更直观理解解决方案的具体构成[^1]。 ---