The smallest truck that will do
Find the smallest capacity that ships all the packages in order within a number of days. About 15 minutes.
The range of answers
Packages must be shipped in the order given, and each day the ship carries a run of packages whose total weight is within its capacity. What is the smallest capacity that gets everything shipped within a number of days?
The capacity can't be below the heaviest package, or that package never fits. And it never needs to be above the total weight, which ships everything in one day. So the answer lies somewhere in that range, and a bigger capacity can only help.
low = max(weights) high = sum(weights)
The capacity is at least 10 and at most 55. Try the middle, 32: it ships in 2 days, within 5. It works, so look lower.
The greedy check
To check a capacity, simulate. Start day one with an empty ship. Put the next package on if it fits, otherwise start a new day. Count the days used. If that is within the limit, the capacity works.
Fill each day as much as possible. Leaving room unused can never reduce the number of days needed, so this is the best plan for that capacity.
def days_needed(capacity):
days, load = 1, 0
for w in weights:
if load + w > capacity:
days += 1
load = 0
load += w
return daysA capacity of 14 needs 6 days, but only 5 are allowed. What do you do next?
- ALook at larger capacities
- BLook at smaller capacities
- CStop and return 14
Show the answer
Look at larger capacities. A larger capacity can only need the same or fewer days.
Smallest ship capacity
weights[i] is the weight of package i. The packages must be shipped in the order given, so each day the ship carries a run of consecutive packages whose total weight is at most the ship's capacity. Return the smallest capacity that ships all the packages within days days.
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5 → 15
1 ≤ packages ≤ 50,000 · 1 ≤ weight ≤ 500 · 1 ≤ days ≤ packages