The goods lift
Moving into a new building. Things are taken up by a freight lift that carries at most X kilograms at a time, and each trip takes ten minutes, so you want as few trips as possible. Things cannot be split: the fridge goes whole. How many trips will be needed?
The movers are used to putting the heaviest thing into the lift first and then adding everything that still fits. In the first sample this gives three trips, although two are enough.
Input
The first line holds n and X (1 ≤ n ≤ 16, 1 ≤ X ≤ 109). The second holds the weights of the things w1, …, wn in kilograms (1 ≤ wi ≤ X).
Output
One number: the smallest number of trips.
Examples
Example 1
6 100 40 40 30 30 30 30
2
Example 2
14 320 72 65 95 38 38 38 38 24 24 24 18 18 12 9
2
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 11 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
“Heaviest first” loses on the first sample. Try going through which things travel together. How many sets of things are there in all, and what do you need to know about a set?
2Hint 2
Suppose the things of a set have already gone up or are standing in the lift. Besides the number of trips, one more number matters for going on. Which? And which of two states with the same set is better?
3The idea
The state is the mask of things that have already gone or are in the current trip. For it we keep a pair: how many trips have been started and how many kilograms are in the last one. Of two pairs the better one has fewer trips, and with equal trips a lighter last one: more will fit into it. A transition adds thing i: if it fits into the current trip, the weight grows; if not, a new trip starts with that thing alone. The answer is the number of trips of the full mask.
4Walkthrough
Why one pair per mask is enough. Any loading order is a sequence of things, and the lift is filled along it greedily: the next thing goes into the current trip if it fits. The best answer is obtained with some order, so it is enough to go through the orders. And orders that have passed through the same set of things differ, for the future, only in the pair “trips, weight of the last”, and the pair with fewer trips or, with equal trips, a smaller weight is no worse: any continuation of the worse pair gives the better one no more trips.
A handy trick: pack the pair into one number trips · (X + 1) + weight. The order of the pairs matches the order of the numbers, and “better” becomes plain “smaller”. There are 216 masks, with up to 16 transitions from each, about a million steps.
In the first sample “heaviest first” loads 40 + 40, then three things of 30, and one more separately: three trips. Yet 40 + 30 + 30 twice will do.
4+Solution
5Complexity
O(2n · n) time and O(2n) memory. This is the bin packing problem, NP-hard in general: for hundreds of things there is no fast exact method, and rules like “heaviest first”, which come with quality guarantees, are what people use.
6Common mistakes
- Heaviest first. A good rule, but not an exact one: the first sample and four hidden tests.
- Only the number of trips in the state. Then there is no way to tell whether the next thing fits into the current trip.
- Keeping all pairs for a mask. Correct but unnecessary: the best one is enough, and there may be many pairs.