题干
AC Code
n, w = map(int, input().split()) # n种类, w核载重
a = [] # [[weight1, value1], [weight2, value2], ...]
for _ in range(n):
a.append(list(map(int, input().split())))
a.sort(key=lambda x: x[1] / x[0], reverse=True)
maxVal = 0
for i in a:
if i[0] < w: # 装得下
maxVal += i[1] # 加钱
w -= i[0] # 减负
else: # 装不下
maxVal += w * i[1] / i[0] # 能装多少装多少
break
print('%.1f' % maxVal)
一道贪心题,考察的是思路,有点像背包问题,本题要求的是最大装载的货物价值,也就是相同装载货物数量情况下的最大价值。
两种考虑思路,第一种,类似于背包问题的考虑角度,</