Write a Java program that solves the 0-1 Knapsack problem with limited repetition both as a pure recursive program and as a dynamic program. Indicate the number of recursive calls both the pure recursive program and the dynamic program make. Print out the maximum value that you can put in the knapsack, its weight, and the items chosen.

The 0-1 knapsack problem with limited repetition is the 0-1 knapsack problem with repetition, but the total amount of each item is limited so that for each item, there is a maximum number of that item available.

Details

The program has two inputs, the file of items and the weight of the knapsack.

The program takes as input a file of items; this file will indicate the name of the item, its value, its weight, and the quantity that are available. The user chooses the file of items using a JFileChooser, as was done in Program 0. It will be a text file in the following format:

Name of item

Unit value of each item

Unit weight of each item

Quantity of each item available

Here is a partial example of such a file:

Porterhouse Steak 20 1 8

Honda Accord 25000 4400 1

Dell Inspiron 15 500 5 6

Paper towels 36 16 5

The program will ask you the maximum weight you can carry in your knapsack. The user should be able to enter this information at runtime. Please be sure to give instructions as to how to do this if its not obvious.

Then there will be two versions of the program that calculates the optimal contents of the knapsack.

The first version will be recursive, it will not be a dynamic program. Keep a count of every recursive call made, and save the total value when the program terminates.

The second version will be a dynamic program, which saves intermediate calculation information to reduce the number of recursive calls. Keep a count of every recursive call made.

Your output file for a given run of the program should contain the following information:

a) The name of the input file containing the set of items (full path name not required, the local name within the directory is fine).

b) The maximum weight of the knapsack.

c) The total value of the knapsack as calculated by the recursive program.

d) The total weight of the knapsack as calculated by the recursive program.

e) The set of items chosen by your recursive program

f) The number of recursive calls in your recursive program

g) The total value of the knapsack as calculated by the dynamic program.

h) The total weight of the knapsack as calculated by the dynamic program.

i) The set of items chosen by your dynamic program

j) The number of recursive calls in your dynamic program.

The above information should be in an output file that is in the same directory as the file containing the set of items.

You should also write a short document not part of the program that explains how your dynamic programming works. This should be in the directory with the source code (or the parent directory of that directory).