10.31

1. A counter-example to “fill the shelf as full as possible”
Let the shelf width limit be L = 6 and let the books arrive in the fixed order
(1) ⟨w=3, h=3⟩, (2) ⟨w=2, h=5⟩, (3) ⟨w=2, h=5⟩.
Greedy packing:
• Shelf 1 holds books 1 + 2 (3+2 ≤ 6) ⇒ height = max(3,5) = 5.
• Shelf 2 holds book 3 ⇒ height = 5.
Total height = 5+5 = 10.
Optimal packing:
• Shelf 1 holds book 1 alone ⇒ height = 3.
• Shelf 2 holds books 2 + 3 ⇒ height = 5.
Total height = 3+5 = 8 (smaller than greedy).

2. Dynamic-programming algorithm
Idea: for every starting position decide how many consecutive books stay on the current shelf.
Let n be the number of books, w[i] / h[i] their width & height (1-based), and L the shelf width.

dp[i] = minimal total height needed for books i…n (with i≤n),
boundary dp[n+1] = 0 (no books – no cost).

for i from n down to 1:
  width = 0, tall = 0, dp[i] = ∞
  for j from i to n:
    width += w[j]
    if width > L: break
    tall = max(tall, h[j])
    dp[i] = min(dp[i], tall + dp[j+1])
answer = dp[1]

Explanation: the inner loop tries every feasible end position j of the first shelf that starts at i; its height is the tallest book seen so far (tall). Adding the optimal cost for the remaining books (dp[j+1]) gives a candidate total; the minimum is stored in dp[i].

Complexity
• Time = O(n²) in the worst case (each pair (i,j) considered once).
• Space = O(n) for the array dp (the input itself can be reused).
Both bounds are acceptable for typical book-shelf sizes, and the algorithm always finds the minimum total shelf height.

Back to Chapter 10