M29949: 贪婪的哥布林

greedy, http://cs101.openjudge.cn/pctbook/M29949/

艾泽拉斯的一只地精 (Goblin，哥布林) 意外地发现了一个废弃的矿洞，里面有数堆不同的矿石（例如铋矿、镔爪矿、亚基矿等）。每一堆矿石都有其总价值和总重量。

哥布林的背包最多只能装下总重量为 W 的物品。幸运的是，这些矿石都是粉末状的，他可以从任何一堆矿石中取出任意一部分（例如取走一堆铋矿的 1/3）。

作为一名贪婪的哥布林，他希望背包里装的矿石总价值尽可能高。请你帮他计算出这个最大总价值。

输入

第一行包含两个整数 N 和 M (1 <= N <= 100, 1 <= M <= 10000)，分别代表矿石的堆数和背包的载重上限。接下来 N 行，每行包含两个整数 v 和 w (1 <= v, w <= 1000)，分别代表这堆矿石的总价值和总重量。

输出

输出一个浮点数，代表能装入背包的最大总价值。结果保留两位小数。

样例输入

样例输出

240.00

提示

tag: greedy

来源

2025 TA-lxy

思路：按性价比取矿石。

python

n, w = map(int, input().split())
candies = []

for _ in range(n):
    p, q = map(int, input().split())
    for _ in range(q):
        candies.append(p / q)

candies.sort(reverse=True)

'''
Degenerate slice indices are handled gracefully: an index that is too large 
is replaced by the string size, an upper bound smaller than the lower bound 
returns an empty string." e.g.:

w = [1,2,3]; sum(w[:6])
Out: 6
'''
value = sum(candies[:w])

print(f"{value:.2f}")

M29949: 贪婪的哥布林 ​

M29949: 贪婪的哥布林