Knapsack Solver

Due: September 28

Objective

Task

For this assignment, you will write a program that solves the "Knapsack Problem". The idea is that you have bag that can only handle a fixed weight limit. You also have a collection of items which each have a value and a weight.

Your goal is to pack your bag with the set of items which maximizes the total value without exceeding the weight limit of the bag.

There is no efficient algorithm for solving this problem, you should just test every possible combination of items, and find the one that fits in the bag, and has the greatest value.

Details

• Your program should take the input file name as the first command line parameter. The first line of the input file is the weight limit of the bag. Each subsequent line contains two integers: the weight and value of an item.
• The second command line parameter should be the number of threads to use. For this program, this needs to be a power of two.
• Your program should report an error if the user does not pass enough arguments, or if the file could not be opened, or if the number of threads is not a positive power of two.
• The most straightforward way to search through the possible pairings is to have an array of boolean true/false values where true means it's in the knapsack and false means it is not. For example, if there are 3 items, then there are 8 different pairings for them:
  • [0,0,0]
  • [0,0,1]
  • [0,1,0]
  • [0,1,1]
  • [1,0,0]
  • [1,0,1]
  • [1,1,0]
  • [1,1,1]
  Your program should loop over every possible packing, figure out if it is over the weight limit, and keep track of the packing which was under the weight limit and had the highest total value. Note that with $N$ items, there are $2^N$ possible packings.
• There are many ways this could be parallelized, but one which will work well is to have the threads take the first few items as being fixed. For example, with the 3 items above, if we used two threads, then we could have the first thread only consider cases where the first item is not in the knapsack, and the second only consider cases where the first item is. That would look like this:

  Thread 0: [0,0,0] [0,0,1] [0,1,0] [0,1,1]

  Thread 1: [1,0,0] [1,0,1] [1,1,0] [1,1,1]

  This can be extended to any number of threads which is a power of two. With four threads, we could break it up like this:

  Thread 0: [0,0,0] [0,0,1]

  Thread 1: [0,1,0] [0,1,1]

  Thread 2: [1,0,0] [1,0,1]

  Thread 3: [1,1,0] [1,1,1]

  The threads should each compute the best packing from their set of possibilities. Afterwards, the main thread should find which thread had the best answer and output that to the user.

Starter Code

In order to facilitate you writing this project, some starter code is provided for you. Feel free not to use this if you want to structure the project in a different way!

The started code is available in knapsack-starter.c.

Test Files

You can test your program with the following input files. After each link is the correct answer for the largest value possible, and associated weight.

• test1.txt
  Weight = 8, Value = 15.
• test2.txt
  Weight = 144, Value = 194.
• test3.txt
  Weight = 249, Value = 319.
• test4.txt
  Weight = 398, Value = 501.
• test5.txt
  Weight = 546, Value = 638.

Analysis

In addition to writing the program, you should test your program on the largest input file, test5.txt, with 1, 2, 4, 8, and 16 threads. For 2-16, report on the speedup and efficiency compared to the single-threaded case.

Submitting

You should submit your program by uploading all of the code, and the analysis to Canvas.