c++动态规划vectordp
时间: 2023-07-08 20:51:30 浏览: 47
好的,您想了解关于使用vector实现动态规划的例子,是吗?
下面是一个使用vector实现的背包问题的动态规划例子:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> w(n + 1); // 物品重量
vector<int> v(n + 1); // 物品价值
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); // dp数组,初始值为0
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j >= w[i]) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[n][m] << endl;
return 0;
}
```
这个例子中,我们使用vector来存储物品重量、物品价值和dp数组。dp数组的大小为(n+1) x (m+1),初始值为0。在循环中,我们使用i和j作为索引,从1开始,分别代表当前物品和当前背包容量。如果当前背包容量可以装下当前物品,则我们选择装或者不装当前物品,取两种情况中最大的价值;否则,我们只能选择不装当前物品。最后,dp[n][m]即为我们所求的最大价值。
希望这个例子能够帮助您理解如何使用vector实现动态规划!