The knapsack problem:

To be written in Java.

3. (25: optional after two required) [Knapsack: programming with post-processing] Write a program code to implement the knapsack algorithm discussed in class, and run it twice against the set of items shown below - once with W 10 and once with W-11. (W is the constraint on total weight.) The program should output the content of the memoization table M[0..n][0..W] each time a row is filled. Additionally, at the end of the program execution, the program should ut the items included in the optimal set and the resulting maximum total value of the items included. Use the "post-processing" approach to retrieve the resulting optimal set of items - see the lecture slide titled "Knapsack: Finding a Solution" to see what the post-processing approach means. Item Value Weight W 10 18 4 22 6 28 W 11 5 7