CMPSC 465, Spr 2013
Assignment 2
Implementing an Exhaustive-search Algorithm for The 0-1 Knapsack Problem

For this assignment, you will implement the exhaustive-search algorithm for the 0-1 knapsack problem that we discussed in class on Wed., Feb. 6. That is, you will generate each subset of the n items, and then calculate the total weight and value of that subset. Figure 3.8 on p. 118 of Levitin, 3e, illustrates the idea of the algorithm, although the subsets of n items are not listed in the order that your instructor's proposed algorithm would generate them.


You will use input redirection to get problem instances from a file. The format of the file is as follows:

The first integer in the file will specify the number of problem instances in the file.

Each problem instance will consist of 4 lines.

The first of these tells how many items, n, there are.
The second gives the maximum capacity, W, of the knapsack.
The third line give the n integer weights, w0, w1, ..., wn-1, separated by spaces.
The fourth line gives the n integer values, v0, v1, ..., vn-1, separated by spaces.

See PA2_data.txt for a sample input file.


For each problem instance, you will

Tell how many subsets of the n items were feasible (did not exceed the knapsack's capacity).
Give the optimal value for this knapsack and set of items.
Give a subset of the n items that has the optimal value and that has minimal weight.
Give the total number of subsets that have the optimal value.

See PA2_output.txt for a sample output file.


For testing, use PA2_data.txt and any other data files of your creation. A sample output for this file is PA2_output.txt.

Final Run:

For the run to hand in, use the data in PA2_final_data.txt.

Partial Code:

The file BF_Knapsack.cpp contains some code that will get you started.


No later than 11:59pm, Tuesday, Feb. 19, put your source code, with the appended runs, into your drop folder at P:\Public\CmpSc 465 Spring 2013\DROP FOLDERS, where P: is your instructor's shared disk. At the beginning of class on Wednesday, Feb. 20, turn in a hardcopy of your code, with appended runs and a signed and dated integrity statement.