道具商店 题目描述 道具商店里有 n 件道具可供挑选。第 i 件道具可为玩家提升ai点攻击力,需要 ci 枚金币才能购买,每件道具只能购买一次。现在你有 k 枚金币,请问你最多可以提升多少点攻击力? 输入格式 第一行,两个正整数 n k ,表示道具数量以及你所拥有的金币数量。 接下来 n 行,每行两个正整数ai , ci ,表示道具所提升的攻击力点数,以及购买所需的金币数量。 输出格式 输出一行,一个整数,表示最多可以提升的攻击力点数。 样例 输入样例1 3 11 99 1 33 2 11 3 输出样例1 132 输入样例2 4 100 10 1 20 11 100 99 40 33 输出样例2 110 数据范围 对于部分测试点,保证 1 ≤k ≤500, 1 ≤ ci ≤500 对于所有测试点,保证 1 ≤n ≤500 , 1 ≤k ≤10^9 , 1 ≤ ai ≤500 , 1 ≤ ci ≤10^9
正确答案：参考程序（Python）：n,k=map(int,input().split());items=[];for _ in range(n):a,c=map(int,input().split());items.append((a,c));#按性价比贪心+小背包。items.sort(key=lambda t:-t[0]/t[1]);best=0;def rec(i,coin,atk):nonlocal best;if coin<0:return;best=max(best,atk);if i==n:retu
试卷来源：202512 CCF-GESP编程能力等级认证C++六级真题