Submit your Java codes via Blackboard. Refer to the grading guidelines posted on Blackboard to understand how the submitted exercises will be graded.
(25) [Knapsack programming with bookkeeping] Write Java code implementing the knapsack algorithm discussed in class, and run it against a set of items (i’s) with values (vi’s) and weights (wi’s) and a total weight limit (W) given in an input text file. An input text file has the following format:
W
v1 w1
v2 w2
v3 w3
…
Your program code should output the content of the memoization table M[0..n][0..W] each time a row is filled. Initialize the memorization table with all −1’s before filling in. Additionally, at the end, the program should output the maximum total value of the items selected and the optimal set of items selected. Use the “bookkeeping” approach to retrieve the resulting optimal set of items – see the lecture slide to see what the bookkeeping approach means. See the provided sample input and sample output files for the output format expected of your program code.
Submit via Blackboard the program source code in one file and the program run output in another file. Your program should work correctly; at least two-thirds of points will be deducted for program that does not work correctly. In addition, your program code should be neatly organized and well commented; there will be many points deducted for program code that is hard to read.
