In this exercise we construct a dynamic programming

Chapter 10, Problem 14E

(choose chapter or problem)

Problem 14E

In this exercise we construct a dynamic programming algorithm for solving the problem of finding a subset S of items chosen from a set of n items where item i has a weight wi , which is a positive integer, so that the total weight of the items in S is a maximum but does not exceed a tixed weight limit W. Let M(j. w) denote the maximum total weight of the items in a subset of the first j items such that this total weight does not exceed w. This problem is known as the knapsack problem.

a)  Show that if wj > w, then M(j, w) = M(j − 1, w).

b)  Show that if  wj ≤ w, then M (j, w) = max ( M ( j − 1, w), wj + M (j — 1. w — wj)).

c)  Use (a) and (b) to construct a dynamic programming algorithm for determining the maximum total weight of items so that this total weight does not exceed W. In your algorithm store the values M(j, w) as they are found.

d)  Explain how you can use the values M(j. w) computed by the algorithm in part (c) to find a subset of items with maximum total weight not exceeding W.

In Exercises 15-18 we develop a dynamic programming algorithm for finding a longest common subsequence of two sequences a1, a2,....,am and b1,b2,..., bn, an important problem in the comparison of DNA of different organisms.