Filling the Shelves
Books must be placed on shelves IN THE GIVEN ORDER. Each book has a thickness and a
height. A shelf holds a consecutive group of books whose thicknesses sum to at most
W. The height of a shelf is the height of its tallest book, and the total height is
the sum over shelves. Print the smallest total height.
W = 6, books (1,3) (2,4) (3,2) -> 4
All three fit on one shelf, thickness 1+2+3 = 6, and the shelf is as tall as the
tallest book, 4.
The order is fixed, which is what makes this a linear problem rather than a packing problem. Sorting the books would let a short one sit under a tall one for free and is not allowed.
## Why filling each shelf greedily fails
Putting as many books as fit on the current shelf before starting a new one looks right and is not. Here is the case:
W = 3, books (1,1) (1,1) (1,5) (1,5)
The greedy fills the first shelf with three books, (1,1) (1,1) (1,5), giving it height
5, then puts the last book on a shelf of its own, height 5. Total 10.
The optimum leaves ROOM on the first shelf: (1,1) (1,1) at height 1, then
(1,5) (1,5) at height 5. Total 6.
That is the whole argument for a table. Leaving a shelf under-filled can pay, because it keeps a tall book off a shelf of short ones, and how much it pays depends on books that have not been reached yet. No local rule sees that.
## The recurrence
Think about which books share the LAST shelf:
dp[0] = 0
dp[i] = min over j of dp[j] + max(height of books j+1 .. i)
for every j such that thickness of books j+1 .. i sums to at most W
Walk j downward from i, accumulating the thickness and the running maximum
height, and stop as soon as the thickness exceeds W. Because every thickness is at
least 1, that inner walk visits at most W books, so the whole thing is O(n W).
Every book has thickness at most W, so a book always fits on a shelf of its own and
the problem is never infeasible.