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? 
  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
Solutions database
capacity                      
max