A depot ships parcels in crates. Every crate holds parcels whose sizes add up to at most
capacity. Write pack_crates(sizes, capacity) that puts every parcel into a crate, using as few
crates as you can. Return a list of crates, each crate a list of parcel indices; every index from
0 to len(sizes) - 1 must appear exactly once. Empty crates are ignored.
The tests build their batches with parcel_batch(m, seed), which returns 3 * m parcel sizes in
the order they arrived, for crates of capacity 1000. It is available in your code, so you can try
it with Run.
How this problem is scored
A packing passes if it is valid and uses no more crates than packing the parcels in arrival order, each into the first crate that still has room (opening a new crate when none has). Its quality (0 to 100) says how much of the gap between that simple packing and the best packing we know you close: 0 matches the simple packing, 100 matches the best one. For every test the best known packing uses exactly as many crates as the total size requires, so it cannot be beaten.
Examples
Input: sizes = [450, 300, 520, 250, 480, 700], capacity = 1000
Output: [[5, 1], [2, 4], [0, 3]]
Explanation: the crates hold 1000, 1000 and 700. Packing in arrival order gives
[0, 1, 3], [2, 4], [5]: also three crates, so both pass.
Input: sizes = parcel_batch(12, 1), capacity = 1000
Output: any valid packing with at most as many crates as the arrival-order packing
Constraints
1 <= len(sizes) <= 300,1 <= sizes[i] <= capacity- Each test must finish in well under a second in your browser. Limit your loops by a number of rounds, not by the clock, so the result is the same on every run.
Goals
- Build a packing greedily and see how the order of the items matters
- Improve a packing with moves and swaps between crates
- Use a lower bound to judge how good a solution is