动态规划算法c++代码
时间: 2023-12-09 20:02:23 浏览: 44
以下是一个简单的动态规划算法的C++代码示例,用于解决背包问题:
```c++
#include <iostream>
#include <vector>
using namespace std;
int knapsack(int W, vector<int> wt, vector<int> val, int n) {
int i, w;
vector<vector<int>> K(n + 1, vector<int>(W + 1));
for (i = 0; i <= n; i++) {
for (w = 0; w <= W; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
int main() {
vector<int> val = {60, 100, 120};
vector<int> wt = {10, 20, 30};
int W = 50;
int n = val.size();
cout << knapsack(W, wt, val, n) << endl;
return 0;
}
```