For this assignment, you will implement two strategies for solving the 0-1 knapsack problem. The first strategy uses the greedy strategy discussed in class by always ordering the choice of items by the value-to-weight ratio. The second strategy should produce the optimal selection using backtracking, which will also be discussed in class. A pseudocode version of this approach is also presented in the textbook.
Your program should read input (using either standard input or files) with the following example format:
35
2000 5 17i LCD
1299 20 iMac
299 8 printer
250 2 4g disk drive
400 2 8g disk drive
1000 20 19i monitor
600 14 17i monitor
400 10 15i monitor
Here, the first integer in the file specifies the maximum weight. Each
following line specifies each item, starting with its value, then its weight,
and ending with its description. Recall that the function
getline(input, str) will read in the rest of the line from
input (or cin) and place it in the string
str.
You should test your algorithms with multiple data files with multiple sizes and compare the speed and selection quality between the two strategies. Mail order catalogs are excellent sources of data. Feel free to share data files with other students.
In addition to submitting your code, you should email me a short report that describes the results of your experiments (about one paragraph). You should also include a technical note of how to run your program.