Closest Cargo Balance
Medium1-D Dynamic Programming
Problem
Crates with positive weights weights must be loaded onto two trucks; every crate goes onto exactly one truck (a truck may end up empty).
Return the smallest possible absolute difference between the two trucks' total weights.
Example 1
- Input:
- weights = [8, 3, 5, 1]
- Output:
- 1
{8} and {3, 5, 1} weigh 8 and 9.
Example 2
- Input:
- weights = [10, 4]
- Output:
- 6
The best is 10 against 4.
Constraints
- 1 ≤ weights.length ≤ 200
- 1 ≤ weights[i] ≤ 100
Hint
Show the first hint
If one truck carries w, the other carries total - w and the difference is |total - 2w|.
Walkthrough
How to approach it
01Clarify before coding
- Can a truck be empty? Yes, so with one crate the difference is its weight.
- Must every crate be loaded? Yes.
- Are weights positive? Yes, which bounds the sums by 200 · 100 = 20,000.
02Brute force
Enumerate all 2^n ways to assign crates and keep the smallest |sumA - sumB|.
Cost: O(2^n · n): hopeless for n = 200.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.