用C++语言解决01背包问题
时间: 2023-09-15 15:16:09 浏览: 40
01 背包问题是一种经典的动态规划问题,可以使用 C++ 来解决。下面是一段示例代码:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int knapsack(vector<int>& w, vector<int>& v, int c) {
int n = w.size();
vector<vector<int>> dp(n + 1, vector<int>(c + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= c; j++) {
if (j < w[i - 1]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
}
}
}
return dp[n][c];
}
int main() {
vector<int> w = {2, 3, 4, 5};
vector<int> v = {3, 4, 5, 6};
int c = 8;
int res = knapsack(w, v, c);
cout << "最大价值为:" << res << endl;
return 0;
}
```
上述代码中,`knapsack` 函数用于求解 01 背包问题,其中 `w` 和 `v` 分别表示物品的重量和价值,`c` 表示背包的容量。在函数中,首先定义了一个二维数组 `dp`,然后通过循环依次计算出每个状态的最大价值。最后返回 `dp[n][c]` 即可。
这段代码的时间复杂度为 $O(nc)$,其中 $n$ 表示物品的数量,$c$ 表示背包的容量。