动态规划背包问题模板c++
时间: 2023-08-09 18:11:03 浏览: 60
以下是一个常见的动态规划背包问题的模板,使用C++实现:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (wt[i - 1] <= w)
dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
else
dp[i][w] = dp[i - 1][w];
}
}
return dp[n][W];
}
int main() {
int W = 10; // 背包容量
vector<int> wt = {2, 3, 4, 5}; // 物品重量
vector<int> val = {3, 4, 5, 6}; // 物品价值
int n = wt.size(); // 物品数量
int maxVal = knapsack(W, wt, val, n);
cout << "背包中能装下的最大价值为: " << maxVal << endl;
return 0;
}
```
这个模板使用二维数组dp来记录状态转移过程。其中dp[i][w]表示前i个物品,在背包容量为w的情况下,能够获得的最大价值。根据状态转移方程,我们可以逐个计算出dp数组的值,最后返回dp[n][W]即为背包中能装下的最大价值。
希望对你有帮助!如果还有其他问题,请随时提问。