Discs for an audiobook

backtracking branch and bound optimization

An audiobook is published on compact discs. A disc holds C minutes; for an ordinary disc that is 80. A chapter cannot be split between discs, and the order of chapters on the discs does not matter to the publisher: there will be a list on the cover. How many discs are needed if the chapters are laid out as economically as possible? The tests include real parts of War and Peace, where a chapter’s length is its reading time at 150 words a minute.

Input

The first line holds the number of chapters n and the disc capacity C in minutes (1 ≤ n ≤ 20, 1 ≤ C ≤ 100). The second holds the lengths of the n chapters, integers from 1 to C.

Output

The smallest number of discs.

Examples

Example 1

Input

13 80
17 38 35 25 12 39 25 11 31 17 30 11 25

Output

Limits

Time · Python: 5000 ms
Time · Go: 1500 ms
Memory: 256 MB
Judging: 12 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

A well-known method is “first fit decreasing”: chapters from long to short, each on the first disc with enough room, and if there is none, on a new one. How many discs does it give on the example? And how many are really needed?

2Hint 2

On the example the greedy method puts 39 + 38 on the first disc, and three minutes on it go to waste. A search is needed: try each chapter on each open disc and on a new one. Which branches can be left unopened?

3The idea

The same prunings as in the article, only the incumbent is a number of discs. Start with the answer of the greedy method. Prune a branch if there are already at least as many discs as the incumbent; if the room on the open discs and on those that can still be opened is not enough for the remaining chapters; do not try a chapter on two discs with the same amount recorded, since that is the same branch; open one new disc, not one for every empty slot. And stop when the incumbent reaches the lower bound.

4Walkthrough

The lower bound here is twofold. The first is ⌈sum / C⌉: there are no fewer discs than the total length requires. The second is the number of chapters longer than half a disc: two such chapters will not fit on one disc, so each needs its own. Take the larger of the two. On the test where all chapters are longer than half a disc, the first bound is 4 and the answer is 5, and the second bound lets the search stop at once.

The order “long first” matters doubly: long chapters are the hardest to place, so dead ends show up at a small depth, while short ones at the end almost always find a place, and the room check quickly proves that nothing better exists.

Bin packing is hard, and the search has no guarantees. The greedy method, on the contrary, does give a guarantee: it needs at most 11/9 of the smallest number of discs plus a small constant; but, as the tests show, an extra disc appears already at about ten chapters.

4+Solution

5Complexity

Exponential in the worst case; on the tests, from one node to several thousand, fractions of a second even in Python.

6Common mistakes

Greed. On six tests out of twelve it needs an extra disc, including the example.
A new disc for every slot. If the search tries to put a chapter “on the second empty disc”, “on the third empty one” and so on, the tree multiplies into identical branches. Empty discs are indistinguishable, and only one should be opened.
Only the bound by the sum. The answer stays correct, but stopping at the bound succeeds less often, and the search has to prove optimality by walking the tree.

Algorithms behind it

TEC Technique Pruning Don’t open branches that certainly hold nothing better: the incumbent, order, symmetry, lower bounds. O(kⁿ) in the worst case 2 problems PAR Technique Branch and bound 38 airports with a direct flight from each to each: a colouring bound shrinks the search from a million nodes to 242. exponential in the worst case 1 problem