Problem: Is the dynamic programming algorithm for the 0-1 knapsack problem that is asked for in Exercise 16.2-2 a polynomial-time algorithm? In addition to the requirements for all problem solutions, support your answer by using the formal definition of complexity class P.

16.2-2: Give a dynamic programming solution to the 0-1 knapsack problem that runs in O (nW ) time, where n is the number of items and W is the maximum weight of items that the thief can put in his knapsack.

The instruction of the solution:

1. describe the algorithm you design for the problem in English,

2. write pseudocode in the style of the CLRS text for your algorithm,

3. define tight asymptotic upper bounds for your algorithms running time.