Dynamic Programming:   Local optimization is no longer global optimization.

 

Example:

Suppose that we have coins of 1, 4 and 6 units.

In his case, a greedy algorithm longer works.

  8 units of change would result in one of ‘6unit’ and two of ‘1 unit’ when

  two of ‘4 unit’ will do. 

 

A different approach is needed.

  A table method.: A table of size d-by-c where d is the number of denominations and

  c is the max amount of change.

 

Amount	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
d[1]=1	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
d[2]=4	0	1	2	3	1	2	3	4	2	3	4	5	3	4	5
d[3]=6	0	1	2	3	1	2	1	2	3	4	2	3	2	3	4

 

  This table shows the minimum number of coins for a given change (indicated by a

  column) using coins up to the one given by a row.

 

  This table can be constructed by row-by-row after the first row has been constructed

  such that

        Table[k,j] = Table[k-1,j] if j<d[k]

                         = min (Table[k-1,j], Table[k,j-d[k]]+1)

                             (Either the previous row or earlier columns of the same row)

  The problem with this method is the huge size of the table.

 

Another example:          Knapsack Problem: Maximization

   We have n items such that each item has a weight and a value.

   We have a bag that can hold only up to a certain maximum weight, a capacity.

   The question: which items to pack so as to maximize the total value.

 

            Items:               1          2          3          4          5

            --------------------------------------------------------

            Weight             1          2          4          6          7

            Value               1          6          18        22        28

 

  One solution: Table Construction

 

Weight	Value	0	1	2	3	4	5	6	7	8	9	10	11	12
1	1	0	1	1	1	1	1	1	1	1	1	1	1	1
2	6	0	1	6	7	7	7	7	7	7	7	7	7	7
4	18	0	1	6	7	18	19	24	25	25	25	25	25	25
6	22	0	1	6	7	18	19	24	25	28	29	40	41	46
7	28	0	1	6	7	18	19	24	28	29	34	40	46	47

 

            After the first row,

Table[k,j] = max(Table[k-1,j], Table[k-1,j-Weight[j]]+Value[j])

                       

            Notice that from a given table entry, we are able to find out all the items included.

            For example, if Table[k,j] > Table[k,j-1] like Table[5,9], then achieving that

maximum requires adding the item-k else the item-k still may be added if

Table[k,j] = Table[k-1,j-Weight[j]]+Value[j]) = Table[k-1,j]

 

Another example: Chained Matrix Multiplication

  Suppose that we have five matrices, M1, M2, M3, M4 and M5 and

  Their respective sizes are 10-by-20, 20-by-5, 5-by-4, 4-by-10 and 10-by-5.

  In this case, should we multiply these four matrices as

   M1(M2(M3*M4))M5 or

   M1(M2(M3*M4)M5) or

   (M1*M2)(M3*M4)M5 or M1(M2*M3)(M4*M5) or   … 

   so as to minimize the total number of necessary multiplications.

 

For this problem, we can construct the following table:

 

               M: Size: n-by-n, Uppertriangular

10-20	20-5	5-4	4-10	10-5
0	1000	1200	1600	1550
	0	400	1200	800
		0	200	300
			0	200
				0

           

              M[j,k] =  min (M[j,m]+M[m+1,k]+d_j-1 * d_m *  d_k )

                            j <= m <= k-1

              d_j   = second dimension size of  M_j  for j=1,2, …, n  and

              d₀  = first dimension size of  M_1.

 

              Example:

                        M[1,4] = min (M[1,1]+M[2,4]+ d₀ d₁ d₄,

                                                M[1,2]+M[3,4]+ d₀ d₂ d₄,

                                                M[1,3]+M[4,4]+ d₀ d₃ d₄)

                                    = min (0+1200+10*20*10, 1000+200+10*5*10, 1200+0+10*4*10)

                                    = min (3200, 1700, 1600)

                        M[2,5] = min (M[2,2]+M[3,5]+ d₁ d₂ d₅

                                                M[2,3]+M[4,5]+ d₁ d₃ d₅

                                                M[2,4]+M[5,5]+ d₁ d₄ d₅ )

                                    = min (0+300+20*5*5,

                                                400+200+20*4*5,

                                                1200+0+20*10*5) = 800

                        M[1,5] = M[1,2]+M[3,5]+10*5*5 and

                        M[3,5] = M[3,3]+M[4,5]+5*4*5.

            So, the optimal sequence is: (M1*M2)*(M3*(M4*M5))

 

            Principle of Optimality

           

            As DP problems amount to making a sequence of n decisions for the overall best

            sequence of decisions, DP problems have this principle that basically says that

            the first decision can be made on the result of a subsequence of decisions made

            on the reduced subproblem associated with making the last n-1 decisions

            (Bottom-up approach).

Equivalently, the overall best sequence of decisions can be made by making the

last decision on the result of making the first n-1 best decisions on a subproblem

associated with making only the first n-1 decisions. (Top-down approach)

 

            Note that using this principle, we are able to eliminate a lot of sub-optimal

            subsequences of decisions.

 

            Example:

            1.   The best M[1,k] for multiplying k chained matrices can be obtained by considering

      only the best M[1,j] and M[j+1,k] for j=1,2,3, …, k-1.

2.      In the case of Knapsack Problem,

Best (n, weight) = optimal solution for n items for the given ‘weight’ capacity    

                          = max (Best(n-1, weight), Best(n-1,weight-W[1])+V[1])

                             where Best(n-1, weight) is the optimal solution for n-1

                             items (all n items except the first item) for the same total

                             capacity  and Best(n-1,weight-W[1])+V[1]) is the optimal

                             solution to be obtained by including the first item to the

     the solution for which Best(n-1,weight-W[1]) needs to be

     obtained which is the optimal solution for the remaining

     n-1 items for the total capacity reduced by the weight of

     the first item.

 

 

  BPE (Balanced Parentheses Expressions) Generation

 

1.      Correspondence between BPE and Binary trees.

·        Dominant pair of parentheses: The leftmost matching pair in a BPE

                                    ( ( ( ) ) ) ( ) ( )

                                    ( ) ( ( ( ) ) ) ( )

                                    ( ( ( ( ( ) ) ) ) )   

·        The dominant pair of a BPE corresponds to the Root of a binary tree.   

·        What is being enclosed inside the dominant pair of parentheses represents the left subtree of the corresponding binary tree.

·        The remainder of a BPE to the right of the dominant pair of parentheses represents the right subtree of the corresponding binary tree. 

·        ‘( )’ corresponds to a node of a binary tree. 

·        Hence, the first and second BPE above corresponds to the following binary tree, respectively:       

 

 

 

 

           

 

 

 

 

                                   

        ( ( ( ) ) ) ( ) ( )                                           ( ) ( ( ( ) ) ) ( )

  

            2.  Generation Sequence of BPE’s

 

                        For the sake of ranking (without actually generating or looking up a table),

                        it is suggested that BPE’s are generated such that in the corresponding

                        binary trees

·        Right subtrees change first with the same left subtree unchanged.

·        Left subtrees change from the largest to the smallest while

·        Right subtrees change from the smallest to the largest.

 

So, the following is some BPE’s in the order of their generations:

 

                                    ( ( ( ( ( ) ) ) ) ) 

                                    ( ( ( ( ) ( ) ) ) )

                                    ( ( ) ) ( ( ( ) ) )

                                    ( ( ) ) ( ( ) ) ( )

                                    ( ( ) ) ( ) ( ( ) )

                                    ( ( ) ) ( ) ( ) ( )

                                    ( ) ( ( ( ( ) ) ) )

                                    ( ) ( ( ) ) ( ) ( )

                                    ( ) ( ) ( ) ( ) ( )

 

3.      Ranking BPE: Calculating the generation sequence of a given BPE

EX:            ( ) ( ) ( ) ( ) ( )               : 42

                  ( ( ( ( ( ) ) ) ) )               :   1

                  ( ) ( ) ( ( ( ) ) )               : 38

                  ( ) ( ) ( ( ) ( ) )               : 39

                  ( ) ( ) ( ( ) ) ( )               : 40

                  ( ) ( ) ( ) ( ( ) )               : 41

·        Convert a given k-pair BPE into an infix expression of integers 1:k.

EX:      ( ) ( ) ( ) ( ) ( )               : 1 2 3 4 5

            ( ) ( ( ( ) ) ) ( )               : 1 4 3 2 5

            ( ( ( ) ) ) ( ) ( )               : 3 2 1 4 5

            ( ( ( ( ( ) ) ) ) )               : 5 4 3 2 1 

·        From the resulting infix expression, we can decompose the given BPE into two parts in terms of infix expressions:

Left subtree (of size leftsize) of the corresponding binary tree

Right subtree (of size k-leftsize-1) of the corresponding binary tree.

·        Compute the rank of each subtree from the corresponding infix expression. 

·        Rank(BPE of size k) = Catalan(k-1)*Catalan(0) + Catalan(k-2)*Catalan(1) + …+ Catalan(leftsize+1)*Catalan(k-leftsize-2)  + (Rank(Leftsubtree)-1)*

             Catalan(k-leftsize-1) + Rank(RightSubtree)

·        EX:

 

( ( ) ) ( ( ( ) ( ) ) ) :

 

size=k=6, leftsize=1

Rank(leftsubtree) = 1, Rank(rightsubtree) = 2

Rank(BPE) = Catalan(5)*Catalan(0) + Catalan(4)*Catalan(1) +

                       Catalan(3)*Catalan(2) + Catalan(2)*Catalan(3) + 2

                   =  42*1 + 14*1 + 5*2 + 2*5 + 2 = 78

 

( ( ) ( ) ) ( ( ( ) ( ) ) )

 

size=k=7, leftsize=2, rightsize=4

Rank(leftsubtree) = 2, Rank(rightsubtree) = 2

Rank(BPE) =  Catalan(6)*Catalan(0) + Catalan(5)*Catalan(1) +

      Catalan(4)*Catalan(2) + Catalan(3)*Catalan(3) + 1*Catalan(4) + 2 =

       132 + 42 + 14*2 + 5*5 + 14 + 2 = 243

 

 

Another Example: Triangulation

 

Given a polygon with n sides, find n-3 chords such that

1. Sum of their distances is minimum.
2. Two chords do not cross each other, equivalently the entire polygon is divided into triangles only.

                                           2

                                        

 

                            1                                  3

 

 

  

0                                                                      4 

   Two chords, 1-4 and 2-4 are drawn in above case.

 

We can represent the problem as minimizing S₀₅   assuming that nodes are sequentially numbered starting with zero and the first subscript represents the starting node number and the second subscript represents the number of nodes of the polygon under consideration.

So, in general,  

S_ij =    min (  S_i,k+1  +  S_i+k,j-k +   D_i,i+k  +  D_i+k,i+j-1 ) 

        1<=k<=j-2 (j-2 choices)  where  D_ij is the distance of a chord connecting two

                                                nodes i and j when they are NOT adjacent

(It is zero if they are adjacent when j= i+1or i-1).

 

For the above polygon, we have     

                 S₀₅ = min (   S₀₂  + S₁₄  +  D₀₁ + D₁₄, 

S₀₃  + S₂₃  +  D₀₂ + D_24,        

                                    S₀₄  + S₃₂  +  D₀₃ + D₃₄ )