 Homework 4Details

(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
 Solve this instance of the knapsack problem using the bottomup dynamic programming algorithm.
Give the optimal cost and a list of the items to take.

How many different optimal solutions does this instance have? Explain how you know.

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?

(4+2+2)
 Solve the instance of the knapsack problem from #1 using the memory function method.
 Indicate which entries in the table are never computed by placing a '' instead of a number.
 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.)
 IDAA 8.4.7 (page 312) (6)
Show all of the intermediate matrices!


