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 thenitems, 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 ofnitems are not listed in the order that your instructor's proposed algorithm would generate them.

Input:

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 theninteger weights, w_{0}, w_{1}, ..., w_{n-1}, separated by spaces.

The fourth line gives theninteger values, v_{0}, v_{1}, ..., v_{n-1}, separated by spaces.

See PA2_data.txt for a sample input file.

Output:

For each problem instance, you will

Tell how many subsets of thenitems were feasible (did not exceed the knapsack's capacity).

Give the optimal value for this knapsack and set of items.

Give a subset of thenitems that has the optimal value and that has minimal weight.

Give the total number of subsets that have the optimal value.

SeePA2_output.txt for a sample output file.

Testing:

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.

Deliverables

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.