Purchasing Milk teaches an important greedy lesson: buying exactly the required amount is not always cheapest. When bundle sizes are powers of two, a larger bundle can cover a leftover amount more cheaply than many small bundles.
Normalize prices first
If a size-4 bundle costs more than two size-2 bundles, we should treat the size-4 bundle as having the cheaper effective cost. This cleanup makes later greedy reasoning safer.
for i from 1 to K - 1:
cost[i] = min(cost[i], 2 * cost[i - 1])After this step, no bundle is obviously worse than replacing it with smaller bundles.
Scan from large to small
For each query amount, keep two variables:
remaining: how much still needs to be covered exactly by the greedy part.currentCost: how much has already been spent.
At every bundle size, buy as many as possible, then also test the option of buying one more current-size bundle to cover the rest.
answer = INF
for size from largest to smallest:
take = remaining / size
currentCost += take * cost[size]
remaining -= take * size
if remaining > 0:
answer = min(answer, currentCost + cost[size])
else:
answer = min(answer, currentCost)Why overbuying matters
If the target is 5 and size-4 plus size-2 is cheaper than size-4 plus one size-1, then the best purchase buys 6 units. The phrase "at least" is the clue.
Practice prompt
Use costs 1: 5, 2: 9, 4: 14, 8: 40. First normalize the costs. Then find the cheapest way to buy at least 7 units.