Dynamic Programming
Document last modified: 
  1. Generate the call tree for the following knapsack algorithm starting with knapsack( 7 ), include capacity in the call.
  2. Show result from each call.
  3. What is the optimal solution?  One A and one B.
  4. Show solutions database.
  int knapsack( capacity )
1 if max ←lookup( capacity ) = NIL then
2    max ← 0
3    for i ← 1 to N
4       if space ← capacity - size[ i ] ≥ 0 then
5          if  tempmax ← knapsack( space ) + value[ i ] > max then
6              max ← tempmax
7     insert( solutions, capacity, max )
8 return max
  1 2 3
item A B C
size 3 4 7
value 4 5 8
                                          knapsack(7) returns 9
                                  -3/9    -4|9        -7\8
                  knapsack(4)  knapsack(3)   knapsack(0)
            -3/4     -4|5               -3|4
knapsack(1)  knapsack(0)  knapsack(0)


Solutions database

capacity 0 1 3 4 7
max 0 0 4 5 9