[SPOJ] Bookcase

Observe that: one of the maximum height is the largest height among all books

There are 3 book cases, let H1 H2 H3 be the maximum height of a book on case 1, 2, 3
WLOG, we always put the book with largest height on case 3
Let W1 be the width of case 1, W2 be the width of case 2
=> the width of case 3 = totalWidth - W1 - W2

Thus, if for every possible values (W1,W2), we could compute min{H1 + H2}, we are done.
This can be computed by DP:
let f[W1, W2] be the minimum value of H1+H2, among all possible arrangements of books such that case 1 has width W1 and case 2 has width W2 and the book width largest height is on case 3.

To see this, consider the 1D version: find a subset of book such that the sum of width is W and the maximum height is minimized. Sort the book in decreasing height. Let F[i][w] = minimum {max height | sum of width = w, using first i books}

If width[i] <= w:
F[i][w]=F[i-1][w] + (width[i] < w?F[i-1][w-width[i]]:(f[i-1][0]+height[i]))

The 2D case is similar: F[i][w1][w2]