$[$Knapsack: programming with bookkeeping$]$ Write Java code implementing the knapsack

algorithm discussed in class, and run it against a set of items $($ i $\text{'}$s$)$ with values $($ v$\_($i$)\text{'}$s$)$ and weights

$($ w$\_($i$)\text{'}$s$)$ and a total weight limit $($ W $)$ given in an input text file. An input text file has the following

format:

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\text{'}$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 on "Knapsack: Finding a Solution" to see what the bookkeeping approach

means and implement the backtracking mechanism. See the provided sample input and sample

output files for the output format expected of your program code. Your program code will be

tested with other test input files as well as this sample input file. Two test input and output files

are also provided.