a. Apply the dynamic programming algorithm to the following instance of the 0-1 knapsack problem:
|
Item
|
Weight
|
Value
|
|
1
|
3
|
$25
|
|
2
|
2
|
$20
|
|
3
|
1
|
$15
|
|
4
|
4
|
$40
|
|
5
|
5
|
$50
|
capacity W = 6. Show your pseudo codes for the dynamic programming solution. You should include a procedure to retrieve an optimal solution.
b. How many different optimal subsets does the instance of part (a) have?
c. In general, how can we use the table generated by the dynamic programming algorithm to tell whether there is more than one optimal subset for the knapsack problem's instance?