贪心算法解决金银岛

解题思路:

注意事项:

参考代码:

def bravery(data,w):
   data.sort(key=lambda x:x[2],reverse=True)
   count = 0
   for i in range(len(data)):
       if w == 0:
           break
       if w >= data[i][0]:
           w -= data[i][0]
           count += data[i][1]
       else:
           count += w*(data[i][1] / data[i][0])
           w = 0
   return round(count,2)
kk = int(input())

for i in range(kk):
   data = []
   w = int(input())
   s = int(input())
   arr = list(map(int,input().split()))
   for j in range(0,2*s,2):
       data.append((arr[j],arr[j+1],arr[j+1]/arr[j]))
   result = bravery(data, w)
   print("%.2f"%result)