数据结构背包问题怎么写
时间: 2023-06-30 19:18:15 浏览: 51
背包问题是一个经典的动态规划问题,其基本思路是将问题分解成若干子问题,通过求解子问题的最优解来得到原问题的最优解。以下是一种常见的背包问题的解法,其时间复杂度为 O(nW),其中 n 表示物品数量,W 表示背包容量。
假设有 n 个物品和一个容量为 W 的背包,第 i 个物品的重量为 w[i],价值为 v[i]。我们定义一个二维数组 dp,其中 dp[j][k] 表示前 j 个物品放入容量为 k 的背包可以获得的最大价值。则对于每个物品 i,我们有以下两种选择:
1. 不放入背包:此时最大价值为 dp[i-1][j]。
2. 放入背包:此时最大价值为 dp[i-1][j-w[i]] + v[i](j >= w[i])。
综上,我们可以得到以下状态转移方程:
```
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++ 代码实现,用于求解 0-1 背包问题:
```
#include <iostream>
#include <vector>
using namespace std;
int knapsack(int W, vector<int>& w, vector<int>& v) {
int n = w.size();
vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (j >= w[i-1]) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n][W];
}
int main() {
vector<int> w = {2, 3, 4, 5};
vector<int> v = {3, 4, 5, 6};
int W = 8;
int ans = knapsack(W, w, v);
cout << ans << endl; // 输出 11
return 0;
}
```