最近在Woodwat镇附近的山上出现了一条冰龙,对城镇造成了极大的威胁,城镇的猎人公会紧急发布了一个S级的悬赏:谁能狩猎这条冰龙,将获取到大量的报酬以及你能带走的所有冰龙素材。这个报酬让所有老猎人都跃跃欲试,其中也包括你。但是冰龙非常强大,要对付它需要准备非常多的道具。但是你的背包总容量是有限的,所以只能装一些最有效的道具。而且有很多猎人都在道具店买这些道具,导致货物紧缺,每种道具每人有限购数量。已知你的背包最大容量为X,你需要在N种道具中挑选,每种道具都有自己的体积V、能造成的伤害K以及限购数量P。 当冰龙被击败时,你便可以从冰龙的身体上获取素材,已知冰龙身上有5种稀有的素材,他们的价格和体积分别为: 名称 体积 价格 龙鳞 2 700 龙血 5 1600 龙牙 3 1000 冰龙冠 200 20000 冰晶 1 10 由于冰龙的体积庞大,可以假设其身体上的素材数量一个人是取之不尽的,同时背包中的道具会永久的占用背包的空间。即若想获得最高的报酬,你必须在保证能够击败冰龙的基础上尽可能的减少对背包容量的占用。 同时已知冰龙的血量为M,请你计算:若你可以消灭冰龙,则计算出能够战胜冰龙时能带走的最大素材价值。若不能消灭冰龙,则输出“Not Kill”。C++
时间: 2024-04-13 22:30:59 浏览: 176
对于这个问题,我们可以使用动态规划来解决。首先,我们定义一个二维数组dp,其中dp[i][j]表示在背包容量为j的情况下,前i种道具能够造成的最大伤害。
然后,我们遍历每种道具,对于第i种道具,我们可以选择不拿,也可以选择拿k个(k <= P[i])。如果选择不拿,则dp[i][j] = dp[i-1][j],即不拿第i种道具时的最大伤害与之前的情况一样。如果选择拿k个,则dp[i][j] = max(dp[i][j], dp[i-1][j-k*V[i]] + k*K[i]),即拿k个第i种道具时的最大伤害。
最终,我们可以遍历所有的背包容量j,找到满足dp[N][j] >= M的最大j值,即为能够战胜冰龙时能带走的最大素材价值。如果找不到满足条件的j值,则输出"Not Kill"。
下面是使用C++实现的代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int X, N, M;
cin >> X >> N >> M;
vector<int> V(N+1), K(N+1), P(N+1);
for (int i = 1; i <= N; i++) {
cin >> V[i] >> K[i] >> P[i];
}
vector<vector<int>> dp(N+1, vector<int>(X+1, 0));
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= X; j++) {
dp[i][j] = dp[i-1][j];
for (int k = 1; k <= P[i]; k++) {
if (j >= k*V[i]) {
dp[i][j] = max(dp[i][j], dp[i-1][j-k*V[i]] + k*K[i]);
}
}
}
}
int max_value = 0;
for (int j = 0; j <= X; j++) {
if (dp[N][j] >= M) {
max_value = max(max_value, j);
}
}
if (max_value == 0) {
cout << "Not Kill" << endl;
} else {
cout << max_value << endl;
}
return 0;
}
```
希望这个解决方案能够帮助到你!如果有任何疑问,请随时提出。
阅读全文