Luogu greedy part of the backpack line segment covers the queue to receive water

P2240 【 Deep base 12. example 1】 Part of the knapsack problem

According to the greedy strategy , First, calculate the cost performance , Then sort by cost performance from large to small , As long as it doesn't reach the weight of the backpack , Just load .

Data structure selection

python No structure , Select two-dimensional array （ Value of goods 、 weight ） Store individual items for easy sorting

num,capacity=map(int,input().split())
arr=[[10000000,0.1] for i in range(101)]

for i in range(num):
    arr[i]=input().split()
    arr[i]=[int(j) for j in arr[i]]
# arr[i].append(i)
# print(arr[i])
arr.sort(key=lambda arr:arr[1]/arr[0],reverse=True)
sum=0
for item in arr:
    if capacity<item[0]:
        sum+=capacity*item[1]/item[0]
        break
    sum+=item[1]
    capacity-=item[0]
print('%.2f'%sum)

P1223 Line up for water

P1803 Line segments cover