3
2
2
4
1
4
[0][1][2][3][4][5]
Brute force · grow the ship one unit at a time
▸1given weights, D2for cap = max(w), max(w)+1, …:3 days = greedy-load at cap4 if days ≤ D: return cap5// first fit is minimal
state
- days3
- total16
warming up the animation
Given package weights that must be shipped in their given order, find the minimum ship capacity such that all packages can be shipped within a given number of days, where each day loads consecutive packages without exceeding the capacity.
▸1given weights, D2for cap = max(w), max(w)+1, …:3 days = greedy-load at cap4 if days ≤ D: return cap5// first fit is minimal
line 1Ship these packages IN ORDER within 3 days. The ship has one capacity; each day it loads packages until the next one would not fit. Smallest capacity that makes the deadline? Brute: try 1, 2, 3, …