贪心金银岛

解题思路:  非常标准的贪心问题

注意事项:

参考代码:

k = int(input())
for _ in range(k):
    w = int(input())     #  口袋承重上限
    s = int(input())     #  种类数
    list = [int(i) for i in input().split()]
    weight = []          #  每种金属的质量
    price = []           #  每种金属的单价
    for i in range(0,2*s,2):
        weight.append(list[i])
        price.append(list[i+1] / list[i])
    value = 0
    ws = w      #  剩余承重
    while ws != 0:
        if len(price) == 0:
            break
        maxprice = max(price)
        maxindex = price.index(maxprice)
        maxweight = weight[maxindex]
        if ws - maxweight >= 0:
            ws -= maxweight
            value += maxprice * maxweight
            price.pop(maxindex)
            weight.pop(maxindex)
        else:
            value += maxprice * ws
            ws = 0
    print('{:.2f}'.format(value))