Expert · Greedy algorithms · 247 of 264
Fractional knapsack
Items can be cut, so you may take part of one. Fill a bag of the given capacity to get the greatest value: take the best value per kilogram first. Print it with two decimals.
Input: n and the capacity, then n lines "weight value". Output: the greatest value, two decimals.
Examples
Input
3 50 10 60 20 100 30 120
Output
240.00
Input
1 5 10 100
Output
50.00
Input
2 100 1 1 2 2
Output
3.00
One more test checks other inputs when you press Check.
Stuck? The idea behind greedy algorithms
Take the best-looking choice at each step and never go back: sorting first usually makes the best choice obvious.
It works only when a local best choice can't spoil the whole answer; for meetings, choosing the one that ends earliest leaves the most room.
meetings = [(1, 4), (3, 5), (0, 6), (5, 7)]
end, count = -1, 0
for s, e in sorted(meetings, key=lambda m: m[1]):
if s >= end:
count += 1
end = e
print(count)Watch for: Sorting by the wrong thing (start instead of end) gives a plausible but wrong answer: try a small case by hand.