Problems 15-7

Let A(i,j) be the optimal solution for first i jobs in the j time. A(1, j) = , if j < .

A(i,j) = .

Problems 15-6

Let d(i,j) be the optimal solution to [i,j]. There are three possibility of  d[i,j], we can choose maximum of them.

1. d(i,j) = d(i,j) + p( (i-1,j-1), (i,j) ) if j > 1
2. d(i,j) = d(i-1,j) + p( (i-1,j), (i,j) )
3. d(i,j) = d(i-1,j+1) + p( (i-1,j+1), (i,j) ), if j < n

Problems 15-5

Solution wanted!

Problems 15-4

Let T(x,c) be the optimal solution rooted in node x and c indicates whether x is choose or not. The recursive formula is T(x, choose) = w(x) + y is x’s child. And T(x, notchoose) = y is x’s child.

Problems 15-3

This is a famous problem.

Problems 15-2

Let c(j) be the optimal solution for first j words. The recursive formula is + penalty(i~j).

Problems 15-1

Sort the point from left ot right. Let be the optimal solution for point 1~j, which start i and left to 1 then right to j. The recursive formula is , i < j-1. And . The base case is trivial.

Exercises 15.5-4

Solution wanted!

Exercises 15.5-3

Solution wanted!

Exercises 15.5-2