Dynamic Programming

solve a problem by solving all possible sub-problems.

N = 5 # of items

M = 17 total capacity

 Name A B C D E Size 3 4 7 8 9 Value 4 5 10 11 13

Exmp:

5A --> value = 20

D + E --> value = 24

Program

Cost[i] = highest value for capacity i

best[i] = last item added

 For j = 1 to N (use first j items only) for i = 1 to M (compute each capacity I) t := Cost [ i - size[j] ] + val [j] If t > Cost[i] then Cost [I] := t; Best [I] := j;

*(on above program, "Cost [ i - size[j] ]" is

best for rest of Knapsack,"val[j]" means that last item is j)

Illustration :

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 0 0 4 4 4 8 8 8 12 12 12 16 16 16 20 20 20 A only A A A A A A A A A A A A A A A 0 0 4 5 5 8 9 10 12 13 14 16 17 18 20 21 22 A,B only A B B A B B A B B A B B A B B 0 0 4 5 5 8 10 10 12 14 15 16 18 20 20 22 24 ABC only A B B A C B A C C A C C A C C 0 0 4 5 5 8 10 11 12 14 15 16 18 20 21 22 24 ABCD only A B B A C D A B B A C C D C C 0 0 4 5 5 8 10 11 13 14 15 17 18 20 21 23 24 ABCDE only A B B A C D E C C E C C D E C

Best choice: C + C + A for M = 17 value = 24

pqr "*" for

Associating Rules.

Want to minimize total # "*" among ways for

(catalan #: )

 ?

Program

Cost[l,r] := min cost for

 for for

In particular:

Weighted Internal Path Length (WIPL)

WIPL = 4*2 + 2*3 + 1*1 + 3*3 + 5*4 + 2*2 + 1*3 = 51

WIPL = 3*1 + (2+2)*2 + (4+1+5+1)*3 = 44

Goal:

Given keys: K1<K2<?<Kn

Frequency: r1 r2 ? rn

Arrange keys in Binary Search Tree to minimize WIPL

Remark:

(1)# binary tree with N node

because

(2)Huffman coding: no need to maintain key order

Algorithm (similar to matrix *)

Minimize ,which is root

 for for

Initialy,