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.
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:
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.
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.
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.
You should submit your program by uploading all of the code, and the analysis to Canvas.
Copyright © 2022 Ian Finlayson | Licensed under a Attribution-NonCommercial 4.0 International License.