Home CPSC 425

Knapsack Problem

Due: October 5th

Objective

To gain experience writing more complex multi-threaded programs with pthreads.

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


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.


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.

ThreadsTimeSpeedupEfficiency
1 N/AN/A
2   
4   
8   
16   

Submitting

When your program works, email the source code and the analysis to ifinlay@umw.edu.

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.