| 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 bottom-up 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!
|
|
|