Homework 4

Details

1. (4+2+2) Consider this instance of the knapsack problem.
   Capacity W = 11 Item weight value
   1 3 27
   2 2 13
   3 4 40
   4 3 32
   5 5 48
   6 7 82
   7 1 12
   
   1. Solve this instance of the knapsack problem using the bottom-up dynamic programming algorithm. Give the optimal cost and a list of the items to take.
   2. How many different optimal solutions does this instance have? Explain how you know.
   3. In general, how can you determine whether or not there is a unique solution to the knapsack problem using the table constructed by the algorithm?
2. (4+2+2)
   1. Solve the instance of the knapsack problem from #1 using the memory function method.
   2. Indicate which entries in the table are never computed by placing a '-' instead of a number.
   3. Clearly indicate (using a circle or square or highlighter) which cells of the table are looked up rather than being recomputed. (That is, the entries that WOULD be computed a second time if the standard recursive algorithm was used.)
3. IDAA 8.4.7 (page 312) (6)
   Show all of the intermediate matrices!