The problem
Parcels with the given weights must go on wagons, and a wagon can carry a total weight of at most cap. Every parcel weighs at most cap. Return the fewest wagons that can carry all of them.
fewest_wagons([2, 3, 3, 5, 6], 10) # 2
fewest_wagons([6, 5, 4, 3, 3, 10, 3], 12) # 3
This is the bin packing problem, which is NP-hard (HARD-1): no fast method is known for many parcels. For a few it is a bitmask DP.
Limits
- Up to 16 parcels. Trying every order (16! is about 2 × 10¹³) is far too slow.
- Splitting into groups with submask loops (lesson 4) is right but makes about 3¹⁶, 43 million, steps for 16 parcels: too slow in Python. Aim for about 2ⁿ · n steps.
Builds on ADDP-4 Bitmask DP.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
11 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | No parcels | Not run | |
| 2 | One parcel | Not run | |
| 3 | All in one wagon | Not run | |
| 4 | Each on its own | Not run | |
| 5 | Two wagons | Not run | |
| 6 | Largest first is not best | Not run | |
| 7 | In the given order is not best | Not run | |
| 8 | Exactly full | Not run | |
| 9 | Eleven parcels | Not run | |
| 10 | Sixteen parcels | Not run | |
| 11 | Sixteen that fill four wagons | Not run |