In class, we discussed the Knapsack Problem as an example of an nP-hard problem. In this problem, you are given a knapsack (or backpack) with an weight limit. You are also given a collection of items, each with a monetary value and a weight. The goal is to find the optimal subset of those items that has the highest total value while also not exceeding the knapsack's weight limit. For example, consider the following items:
| value ($) | weight (lbs) | descriptor |
|---|---|---|
| 5000 | 3 | tiara |
| 2200 | 5 | coin collection |
| 2100 | 40 | tv |
| 2000 | 8 | laptop |
| 1200 | 10 | silverware |
| 800 | 25 | stereo |
| 600 | 1 | cell phone |
| 300 | 4 | clock |
If the knapsack had a weight limit of 10 pounds, the optimal subset would be {tiara, coin collection, cell phone} with a total value of $7,800 (and a total weight of 9 pounds). Conversely, if the knapsack had a weight limit of 50 pounds, the optimal subset would be {tiara, coin collection, laptop, silverware, cell phone, clock} with a total value of $11,300 (and a total weight of 31 pounds).
For the first part of this assignment, you are to write a Java program to solve the Knapsack Problem using a generate & test approach. Your driver class should prompt the user for the knapsack weight limit and the name of a file containing info on items (each line consists of an item's value, followed by its weight, followed by a descriptor). See knap.txt, for example. The program should evaluate every possible subset of the items and display the optimal subset along with its value. For example:
Enter the knapsack weight limit: 10 Enter the items file: knap.txt tiara coin collection cell phone Total Value = $7800
When designing your solution, you must create a class named KnapsackItem for storing and accessing item info (value, weight and descriptor), and a class named Knapsack that has at least two methods: an addItem method that adds a KnapsackItem to the contents, and a findOptimalSubset method that finds the optimal subset of KnapsackItems and returns them in an Set. Your driver class should handle all the input and output, including prompting the user for the weight limit and file name, as well as displaying the items in the optimal subset along with the total value. You are free to create additional classes and/or add other methods as needed.
KnapsackTimer is a provided driver class that can be used to measure the time your solution takes on successively larger lists of items. As written, it constructs lists ranging from 20 to 30 items and uses the StopWatch class to measure the time for each solution. Use this program to generate timings that confirm the O(2N) behavior of your generate & test solution. Your submission should include a separate document that lists the timings and briefly explains how they demonstrate O(2N) efficiency. Note: if your particular computer is extra fast (or extra slow), you may need to adjust the range of sizes to obtain reasonable timings.