用C++写一个动态规划
时间: 2023-12-29 07:53:18 浏览: 25
动态规划是一种解决最优化问题的算法,其基本思想是将原问题划分为若干个子问题,通过求解子问题的最优解来得到原问题的最优解。
以下是一个用C++实现的动态规划的例子,解决了背包问题(0-1背包问题):
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int knapsack(int n, int W, vector<int>& wt, vector<int>& val) {
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 (wt[i-1] <= j) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]] + val[i-1]);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n][W];
}
int main() {
int n = 3; // 物品数量
int W = 50; // 背包容量
vector<int> wt = {10, 20, 30}; // 每个物品的重量
vector<int> val = {60, 100, 120}; // 每个物品的价值
int res = knapsack(n, W, wt, val);
cout << "The maximum value that can be obtained: " << res << endl;
return 0;
}
```
该程序中,我们使用一个二维数组dp来保存子问题的解,其中dp[i][j]表示前i个物品放入容量为j的背包中能够获得的最大价值。状态转移方程为:
```
dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]] + val[i-1]);
```
其中,wt[i-1]和val[i-1]分别表示第i个物品的重量和价值。如果第i个物品的重量小于等于j,那么有两种选择:放入背包或不放入背包。如果放入背包,那么背包的剩余容量为j-wt[i-1],此时能够得到的最大价值为dp[i-1][j-wt[i-1]] + val[i-1];如果不放入背包,那么背包的容量不变,此时能够得到的最大价值为dp[i-1][j]。因此,dp[i][j]取这两种情况的最大值。
最后,程序输出的结果即为放入物品后能够获得的最大价值。