Chapter 15 Answers

Memoization

Question

• Draw the recursion tree for fibDP( 6 ) and the solutions dictionary.

  key	0	1	2	3	4	5	6
  solution	0	1	1	2	3	5	8

                            fibDP(6)
                            /     
                     fibDP(5) 
                         /         
                  fibDP(4)  
                      /    
              fibDP(3)  
                  /        
          fibDP(2) 
              /    \
  lookup 1    lookup 0 

   

• How many calls? 5
• What is the O running time in terms of the calls? O(n)

Brute force/exhaustive search

Items     1 2 3 item A B C size 7 3 4 value $42 $12 $40

Exhaustive search - {A,B} optimal solution, $54 Subset Total size Total value Æ 0 $0 {A} 7 $42 {B} 3 $12 {C} 4 $40 {A,B} 10 $54 {A,C} 11 $82 {B,C} 7 $52 {A,B,C} 14 not feasible

Question: Suppose our knapsack held W=13? What is the optimal solution? {A,C}, $82

Discrete Knapsack problem - an optimization

Question

1. What is returned from path <3,3,4,4,3>? The value 22. Is that optimal? No, 24 is optimal.
2. Generate the first few (7 or 8) recursive calls to knapsack( 17 ).

   	int knapsack( capacity )
   1	max ¬ 0
   2	for i ¬ 1 to N	-- N number of items
   3	if space ¬ capacity - size[ i ] ≥ 0 then	-- Room for item i
   4	if  tempmax ¬ knapsack( space ) + value[ i ] > max then
   5	max ¬ tempmax
   6	return max

   knapsack(17)                              -3    /                                 knapsack(14)                            -3     /                                    knapsack(11)                          -3     /                                 knapsack(8)                    -3   /               \  -4                           knapsack(5)     knapsack(4)              -3   /     \   -4         -3     /       \  -4 knapsack(2) knapsack(1) knapsack(1)  0

   1 2 3 4 5 item A B C D E size 3 4 7 8 9 value 4 5 10 11 13

                            

3. Is this a greedy algorithm? Only in that the maximum value for a given capacity is always returned; it does not guide the solution. Does it always choose the best choice to solve for a solution or do extra work? Much extra work.

	int knapsack( capacity )
1	if max ¬ lookup(capacity) = NIL then	-- if exists use max value for capacity
2	max ¬ 0	-- otherwise compute value for capacity
3	for i ¬ 1 to N	-- N is number of items
4	if space ¬ capacity - size[ i ] ≥ 0 then	-- Room for item i
5	if  tempmax ¬ knapsack( space ) + value[ i ] > max then
6	max ¬ tempmax
7	insert( solutions, capacity, max )	-- Store max keyed on capacity
8	return max

1 2 3 4 5 item A B C D E size 3 4 7 8 9 value 4 5 10 11 13

Solutions database for knapsack( 17 ) capacity 0 1 2 3 4 5 6 7 8 9 10 11 13 14 17 max 0 0 0 4 5 5 8 10 11 13 14 15 18 20 24

Question

1. Does the algorithm exhibit greedy behavior? Sorta. It always uses the current maximum value for a given capacity. The solution space is reduced by looking up previously computed maximums.
2. Why doesn't 12, 15, or 16 occur in the solutions database? For capacity 17 - size[i] was not 12, 15, or 16.
3. Is the above recursion tree complete for the dynamically programmed version? Compare <17, 9, 6, 3> and <17, 13, 6>. Yes. The solution for capacity 6 was computed for <17,9,6,3>.
4. Why does the dynamically programmed recursion tree above differ from the brute force tree below? In the above case, value for capacity 6 already computed in <17, 9, 6, 3>, not recomputed for <17, 13, 6, 3>.
5. What would be returned from <17, 14, 11, 7>? 4+4+5+10=23