Exercise Lover

July 9, 2007

Problems 15-7

Filed under: Problem 15 — yuhanlyu @ 10:28 am

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

A(i,j) = max( A(i-1,j), (A(i-1, j-t_i) + p_i)[d_i < j] ).

Problems 15-6

Filed under: Problem 15 — yuhanlyu @ 10:26 am

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

Filed under: Problem 15 — yuhanlyu @ 10:21 am

Solution wanted!

Problems 15-4

Filed under: Problem 15 — yuhanlyu @ 10:19 am

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) + \sum_y T(y, notchoose) y is x’s child. And T(x, notchoose) = \sum_y max( T(y,choose), T(y,notchoose)) y is x’s child.

Problems 15-3

Filed under: Problem 15 — yuhanlyu @ 10:15 am

This is a famous problem.

Problems 15-2

Filed under: Problem 15 — yuhanlyu @ 10:14 am

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

Problems 15-1

Filed under: Problem 15 — yuhanlyu @ 10:12 am

Sort the point from left ot right. Let P_{i,j} be the optimal solution for point 1~j, which start i and left to 1 then right to j. The recursive formula is P_{i,j} = P_{i,j-1} + D(p_{j-1},p_j),, i < j-1. And P_{j-1,j} = \min_k P_{k,j-1} + d(p_k,p_j). The base case is trivial.

Blog at WordPress.com.