首页动态规划法求解0-1背包 python

动态规划法求解0-1背包 python

时间: 2025-06-28 18:15:24 浏览: 10

### 使用Python实现动态规划解决0-1背包问题对于0-1背包问题，目标是在不超过背包容量的前提下使所选物品的价值最大化。该问题可以通过动态规划来高效求解。 #### 动态规划的核心思想动态规划方法通过构建一个二维数组`dp[i][j]`表示前i个物品放入容量为j的背包可以获得的最大价值。状态转移方程如下： \[ dp[i][j]=\begin{cases} dp[i−1][j], & \text{if } j<w_i \\ max(dp[i−1][j],v_i+dp[i−1][j-w_i]),& \text{otherwise} \end{cases}\] 其中\(w_i\)代表第i件商品重量,\(v_i\)代表第i件商品价值[^2]。下面是具体的Python代码实现： ```python def knapsack(weights, values, capacity): n = len(values) # 创建并初始化dp表 dp = [[0]*(capacity + 1) for _ in range(n + 1)] # 填充dp表格 for i in range(1, n + 1): for w in range(capacity + 1): if weights[i - 1] <= w: dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]) else: dp[i][w] = dp[i - 1][w] return dp[n][capacity] weights = [2, 3, 4, 5] # 物品重量列表 values = [3, 4, 5, 8] # 对应物品价值列表 capacity = 5 # 背包最大承重能力 print(f"Maximum value we can obtain is {knapsack(weights, values, capacity)}") # 输出结果 ``` 此程序定义了一个名为`knapsack()`的功能函数接收三个参数——物品重量列表、对应的物品价值以及背包的最大承载量；返回的是能获得的最大总价值。最后打印出了当给定一组特定输入时所能得到的最佳解决方案。

阅读全文