c++动态规划背包问题
时间: 2023-07-07 09:20:20 浏览: 59
好的,背包问题是动态规划中比较经典的问题之一,它有 0/1 背包和完全背包两种情况。下面我简要介绍一下 0/1 背包问题的动态规划解法。
假设有 n 个物品,每个物品的重量为 w[i],价值为 v[i],背包最大承重为 W。定义一个二维数组 dp[i][j],表示前 i 个物品在重量不超过 j 的情况下的最大价值。则转移方程为:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]), j >= w[i]
dp[i][j] = dp[i-1][j], j < w[i]
其中第一行表示不选任何物品的情况,第二行表示背包无法承受当前物品的重量。最终的结果为 dp[n][W]。
在实现时,可以使用一维数组优化空间复杂度。具体实现可以参考下面的 C++ 代码:
```cpp
int n, W;
int w[N], v[N];
int dp[N];
int main() {
cin >> n >> W;
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++) {
for (int j = W; j >= w[i]; j--) {
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}
cout << dp[W] << endl;
return 0;
}
```
该算法的时间复杂度为 O(nW),可以通过滚动数组进一步优化空间复杂度。