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:
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.
When your program works, email the source code and the analysis to firstname.lastname@example.org.
Copyright © 2019 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.