暗黑游戏中,装备直接决定玩家人物的能力。可以使用 Pg 和 Rune 购买需要的物品。暗 黑市场中的装备,每件有不同的价格(Pg 和 Rune)、能力值、最大可购买件数。Kid 作为暗 黑战网的一个玩家,当然希望使用尽可能少的 Pg 和 Rune 购买更优的装备,以获得最高的能 力值。请你帮Kid计算出现有支付能力下的最大可以获得的能力值。 输入格式: 第一行,三个整数 N,P,R,分别代表市场中物品种类,Pg 的支付能力和 Rune 的支付能力。 第 2..N+1 行,每行四个整数,前两个整数分别为购买此物品需要花费的 Pg,Rune,第 三个整数若为 0,则说明此物品可以购买无数件,若为其他数字,则为此物品可购买的最多 件数(S),第四个整数为该装备的能力值。 输出格式: 仅一行,一个整数,最大可获得的能力值。c语言代码实现
时间: 2024-03-18 14:39:23 浏览: 17
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1005
int n, P, R, ans;
int pg[MAXN], rune[MAXN], num[MAXN], val[MAXN];
int f[MAXN][MAXN];
int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d%d%d", &n, &P, &R);
for (int i = 1; i <= n; i++)
scanf("%d%d%d%d", &pg[i], &rune[i], &num[i], &val[i]);
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= P; j++) {
for (int k = 0; k <= R; k++) {
f[j][k] = max(f[j][k], f[j - pg[i]][k - rune[i]] + val[i]);
}
}
}
printf("%d\n", f[P][R]);
return 0;
}
```
相关问题
写出满足如下要求的代码:暗黑游戏 暗黑游戏中,装备直接决定玩家人物的能力。可以使用 Pg 和 Rune 购买需要的物品。暗 黑市场中的装备,每件有不同的价格(Pg 和 Rune)、能力值、最大可购买件数。Kid 作为暗 黑战网的一个玩家,当然希望使用尽可能少的 Pg 和 Rune 购买更优的装备,以获得最高的能 力值。请你帮Kid计算出现有支付能力下的最大可以获得的能力值。 输入格式: 第一行,三个整数 N,P,R,分别代表市场中物品种类,Pg 的支付能力和 Rune 的支付能力。 第 2..N+1 行,每行四个整数,前两个整数分别为购买此物品需要花费的 Pg,Rune,第 三个整数若为 0,则说明此物品可以购买无数件,若为其他数字,则为此物品可购买的最多 件数(S),第四个整数为该装备的能力值。 输出格式: 仅一行,一个整数,最大可获得的能力值。
以下是满足要求的 Python3 代码实现:
```python
n, p, r = map(int, input().split())
items = []
for _ in range(n):
pg, rune, s, value = map(int, input().split())
if s == 0:
items.append((pg, rune, float('inf'), value))
else:
items.append((pg, rune, s, value))
dp = [[0 for _ in range(r+1)] for _ in range(p+1)]
for i in range(n):
pg, rune, s, value = items[i]
for j in range(p, pg-1, -1):
for k in range(r, rune-1, -1):
for t in range(1, s+1):
if j >= pg*t and k >= rune*t:
dp[j][k] = max(dp[j][k], dp[j-pg*t][k-rune*t] + value*t)
print(dp[p][r])
```
思路解析:
这是一道典型的 0/1 背包问题,但是和一般的 0/1 背包问题的不同点在于这里的物品的数量是有限制的,即每种物品最多只能买 $S$ 个。我们可以把这个限制拆分成 $S$ 个 0/1 背包问题来做。
具体来说,我们可以把每种物品拆成 $S$ 个物品,每个物品的重量和价值都是原来的重量和价值乘以 $t$,其中 $t$ 从 $1$ 取到 $S$。然后,我们就可以按照普通的 0/1 背包问题的方式来处理了。
时间复杂度分析:
一共有 $N$ 种物品,每种物品最多可以拆成 $S$ 个物品。因此,我们总共需要处理的物品数量是 $O(NS)$。对于每个物品,我们需要在 $P$ 和 $R$ 的范围内进行 0/1 背包。因此,总时间复杂度是 $O(NPSR)$。
写出满足如下要求的C++代码:暗黑游戏 暗黑游戏中,装备直接决定玩家人物的能力。可以使用 Pg 和 Rune 购买需要的物品。暗 黑市场中的装备,每件有不同的价格(Pg 和 Rune)、能力值、最大可购买件数。Kid 作为暗 黑战网的一个玩家,当然希望使用尽可能少的 Pg 和 Rune 购买更优的装备,以获得最高的能 力值。请你帮Kid计算出现有支付能力下的最大可以获得的能力值。 输入格式: 第一行,三个整数 N,P,R,分别代表市场中物品种类,Pg 的支付能力和 Rune 的支付能力。 第 2..N+1 行,每行四个整数,前两个整数分别为购买此物品需要花费的 Pg,Rune,第 三个整数若为 0,则说明此物品可以购买无数件,若为其他数字,则为此物品可购买的最多 件数(S),第四个整数为该装备的能力值。 输出格式: 仅一行,一个整数,最大可获得的能力值。
以下是满足要求的 C++ 代码实现:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110, M = 1010;
int n, P, R;
int dp[M][M];
struct Item {
int pg, rune, s, value;
} items[N];
int main() {
cin >> n >> P >> R;
for (int i = 0; i < n; i++) {
cin >> items[i].pg >> items[i].rune >> items[i].s >> items[i].value;
if (items[i].s == 0) items[i].s = 0x3f3f3f3f;
}
for (int i = 0; i < n; i++) {
Item &item = items[i];
for (int j = P; j >= item.pg; j--) {
for (int k = R; k >= item.rune; k--) {
for (int t = 1; t <= item.s && t * item.pg <= j && t * item.rune <= k; t++) {
dp[j][k] = max(dp[j][k], dp[j-t*item.pg][k-t*item.rune] + t*item.value);
}
}
}
}
cout << dp[P][R] << endl;
return 0;
}
```
思路解析:
这道题目是一道二维费用的 0/1 背包问题。跟一般的 0/1 背包问题不同的是,这里的物品的数量是有限制的,即每种物品最多只能买 $S$ 个。因此,我们需要把每种物品拆成 $S$ 个物品,每个物品的重量和价值都是原来的重量和价值乘以 $t$,其中 $t$ 从 $1$ 取到 $S$。这样,我们就可以按照一般的 0/1 背包问题的方式来处理了。
具体来说,我们可以定义 $dp[i][j][k]$ 表示前 $i$ 种物品,使用 $j$ 的 Pg 和 $k$ 的 Rune 可以获得的最大能力值。对于第 $i$ 种物品,我们需要枚举购买的件数 $t$,然后我们就可以按照一般的 0/1 背包问题的方式来更新状态了:
$$dp[i][j][k] = \max\{dp[i-1][j-t\cdot pg][k-t\cdot rune] + t\cdot value\}$$
其中 $t$ 的取值范围是 $[1, S]$,且必须满足 $t\cdot pg \le j$ 和 $t\cdot rune \le k$。
时间复杂度分析:
一共有 $N$ 种物品,每种物品最多可以拆成 $S$ 个物品。因此,我们总共需要处理的物品数量是 $O(NS)$。对于每个物品,我们需要在 $P$ 和 $R$ 的范围内进行 0/1 背包。因此,总时间复杂度是 $O(NP^2R^2S)$。由于 $P$ 和 $R$ 的范围很小,因此我们可以通过使用滚动数组或者进行空间优化来降低空间复杂度,但时间复杂度不会发生改变。