我要招人

去企业版

首页 > 试题广场 >

古代仪式的准备

[编程题]古代仪式的准备

热度指数：529 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

作为一位资深的炼金术士，你正在为一场能够扭转星辰轨迹的古代仪式做最后的准备。

仪式的成功与否，取决于你能否在法阵中注入足够强大的魔力。

幸运的是，你的储藏室里有多种珍稀的魔法媒介，每一种都能在激活时释放出磅礴的能量。

然而，激活这些媒介需要消耗你自身的法力值（Mana）。你的法力储备是有限的，因此，你必须在众多媒介中做出最经济、最有效的选择，以确保仪式能够顺利启动。

给定仪式的最低魔力能源需求 $E_{req}$ ，以及你当前拥有的总法力值上限 $M_{budget}$ 。现在有 $n$ 种可用的魔法媒介，对于第 $i$ 种媒介，它能提供 $E_i$ 点魔力能源，同时需要消耗 $M_i$ 点法力值来激活。

你的任务是，在总法力消耗不超过 $M_{budget}$ 的前提下，找出一个媒介组合，使其提供的总魔力能源 $E_{total}$ 满足 $E_{total} \ge E_{req}$ 。

输入描述:

输入的第一行包含三个整数 , , 。

* ：仪式所需的最小魔力能源 ()。
* ：你的法力值上限 ()，保证是  的整数倍。
* ：可用魔法媒介的总数量 ()。

接下来的  行，每行包含两个整数  和 。

* ：第  种媒介能提供的魔力能源 ()。
* ：激活第  种媒介所需的法力值 ()，保证是  的整数倍。

输出描述:

1.  请输出能够满足魔力能源需求 () 的**最小法力总消耗**，以及在该消耗下所能获得的**最大魔力能源**。
2.  如果在法力值上限内无法满足仪式的最低能源需求，则输出 `0 0`。

示例1

输入

输出

430 2300

说明

仪式需要至少  点魔力能源，你的法力上限为 。

*   **媒介1**: 提供  能源，消耗  法力。
*   **媒介2**: 提供  能源，消耗  法力。
*   **媒介3**: 提供  能源，消耗  法力。

最佳策略是选择**媒介2**和**媒介3**。
总消耗法力为 ，在你的法力上限  之内。
总获得能源为 ，满足了最低  的需求。
这是所有满足条件的组合中，法力消耗最小的方案。

示例2

输入

输出

0 0

说明

仪式需要至少  点魔力能源，你的法力上限为 。
分析所有媒介组合可以发现，没有任何一种组合方式能够在消耗不超过  法力的前提下，提供超过  点的魔力能源。因此，仪式无法启动，输出 `0 0`。

备注:

本题由牛友@Charles 整理上传

算法知识视频讲解

Python3

牛客665706818号

ereq,budget,n = map(int,input().split())

costmin = 0

etotal = 0

energy = []

cost = []

for i in range(n):

energyi, costi = map(int,input().split())

energy.append(energyi)

cost.append(costi)

dp = [0]*(budget+1) # 初始化dp数组表示budget法力消耗下提供的最大能源

for i in range(n): # 遍历每一种魔法媒介

for j in range(budget,cost[i]-1,-1): # 从大到小遍历法力值消耗的总值从小到大会重复选择同一个魔法媒介

if dp[j] < dp[j-cost[i]] + energy[i]: # 当前提供的最大能源<使用当前媒介后提供的最大能源更新为使用当前媒介

dp[j] = dp[j-cost[i]] + energy[i]

for i in range(budget+1): # 从小到大寻找满足能源要求所消耗的最小法力值

if dp[i] >= ereq:

costmin = i

etotal = dp[i]

break

print(costmin,etotal)

发表于今天 16:35:41 回复(0)

牛客759207447号

升级版背包

发表于 2025-09-10 20:28:55 回复(0)

提交观点

问题信息

难度：

2条回答 2收藏 21浏览

古代仪式的准备

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

相关试题