Fewest Ferry Crossings
A ferry carries at most limit kilograms on each crossing. Crate i weighs crates[i] kilograms, and no crate is heavier than limit. A crossing can carry any group of crates whose weights add up to at most limit; crates cannot be split.
Return the fewest crossings needed to carry every crate. With no crates, return 0.
Example 1
crates [2,7,4,2,3,3,2]
limit 8
returns 3
Send the 7 alone, then 4 + 2 + 2 and 3 + 3 + 2, both exactly 8 kilograms. Loading the heaviest crates first would need four crossings.
Example 2
crates [6,6,6]
limit 10
returns 3
No two crates fit together, so each needs its own crossing, even though the total is only 18.
Constraints
0 <= len(crates) <= 101 <= crates[i] <= limit <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.