辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。并写出代码
时间: 2024-02-09 16:08:41 浏览: 27
好的,这是一个经典的背包问题,可以使用动态规划算法来解决。以下是C++的代码示例:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m; // n是草药的数量,m是背包的容量
vector<int> v(n); // 存储草药的价值
vector<int> w(n); // 存储草药的重量
for (int i = 0; i < n; i++) {
cin >> v[i] >> w[i];
}
vector<vector<int>> dp(n + 1, vector<int>(m + 1)); // dp[i][j]表示前i个草药,背包容量为j时的最大价值
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j >= w[i - 1]) { // 如果当前背包容量可以放下第i个草药
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]); // 取放或不放第i个草药的最大值
} else {
dp[i][j] = dp[i - 1][j]; // 否则只能不放第i个草药
}
}
}
cout << dp[n][m] << endl; // 输出最大价值
return 0;
}
```
以上代码使用一个二维数组dp来存储状态,其中dp[i][j]表示前i个草药,背包容量为j时的最大价值。在每次迭代中,我们判断当前背包容量是否可以放下第i个草药,如果可以,则取放或不放第i个草药的最大值,否则只能不放第i个草药。最后输出dp[n][m]即可得到最大价值。