用动态规划法求解0-1背包问题
时间: 2025-05-20 16:36:14 浏览: 17
### 动态规划求解0-1背包问题
动态规划是一种通过把复杂问题分解成子问题来解决问题的方法。在0-1背包问题中,目标是在给定容量的背包下最大化所装物品的总价值[^1]。
#### 状态定义
设 `dp[i][w]` 表示前 `i` 个物品,在背包容量为 `w` 的情况下能够获得的最大价值。状态转移方程如下:
如果第 `i` 个物品不放入背包,则其最大价值等于前 `i-1` 个物品在相同容量下的最大价值;
如果第 `i` 个物品放入背包,则其最大价值等于前 `i-1` 个物品在剩余容量 `(w - weight[i])` 下的最大价值加上当前物品的价值 `value[i]`。
最终的状态转移方程可以表示为:
\[ dp[i][w] = \max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) \]
其中,`weight[i]` 是第 `i` 个物品的重量,`value[i]` 是第 `i` 个物品的价值。
#### 初始化条件
初始化时,当背包容量为 0 或者没有物品可选时,最大价值均为 0,即 \( dp[0][w] = 0 \) 和 \( dp[i][0] = 0 \)[^3]。
#### 时间与空间优化
为了减少内存消耗,可以通过滚动数组的方式将二维数组压缩为一维数组。此时需要注意遍历顺序应从后向前更新,以避免覆盖未使用的旧数据[^2]。
以下是基于 C++ 的代码实现:
```cpp
#include <vector>
#include <algorithm>
using namespace std;
// 参数说明:
// weights: 物品重量列表
// values: 物品价值列表
// capacity: 背包容量
// 返回值:最大价值
int knapsack_01(const vector<int>& weights, const vector<int>& values, int capacity) {
int n = weights.size();
vector<int> dp(capacity + 1, 0);
for (int i = 0; i < n; ++i) {
for (int w = capacity; w >= weights[i]; --w) {
dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}
```
此代码实现了经典的0-1背包问题解决方案,利用了一维数组进行空间优化,并按照逆序方式更新状态表以确保每次计算都依赖于之前的结果[^2]。
---
阅读全文
相关推荐
















