Dynamic Programming

powered by FreeFind

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