Home CPSC 425

Knapsack Solver

 

Due: September 28

 

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


 

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.


 

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

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.