请用c++语言写出这道题的代码
时间: 2024-11-09 10:30:28 浏览: 5
c++语言编写的玫瑰花代码
在这个问题上,我们可以使用贪心策略,不过由于题目涉及到背包问题,最直接的方法还是动态规划。以下是使用 C++ 编写的动态规划解决方案:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int maxValue(int n, int m, vector<pair<int, int>>& requests) {
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); // 初始化动态规划矩阵
for (int i = 1; i <= n; ++i) { // 遍历所有请求
for (int j = 1; j <= m; ++j) { // 遍历所有体力值
if (requests[i - 1].second <= j) { // 当请求体力消耗小于等于剩余体力
dp[i][j] = max(dp[i][j], dp[i - 1][j] + requests[i - 1].first); // 加入请求的价值
}
dp[i][j] = max(dp[i][j], dp[i - 1][j]); // 如果不加入请求,保持当前状态
}
}
return dp[n][m]; // 返回最大价值
}
int main() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> requests(n);
for (int i = 0; i < n; ++i) {
cin >> requests[i].first >> requests[i].second;
}
int result = maxValue(n, m, requests);
cout << "硫化氢最多能获得的价值是: " << result << endl;
return 0;
}
```
这段代码首先定义了一个二维动态规划数组 `dp`,然后通过嵌套循环遍历请求和体力值,根据请求的条件更新最大价值。最后在 `main()` 函数中读入数据并调用 `maxValue` 函数计算结果。
阅读全文