Heuristics for the Knapsack Problem

Loading...
Thumbnail Image
Authors
Gilbertson, Claire
Advisor
Holly Zullo
Mark Parker
Jeffrey Morris
Editor
Date of Issue
2008-04-01
Subject Keywords
Publisher
Citation
Series/Report No.
item.page.identifier
Title
Heuristics for the Knapsack Problem
Other Titles
Type
thesis
Description
Abstract
We explore the knapsack problem where the goal is to maximize the value of packed objects for a certain container. The knapsack problem is NP-complete which means the time needed to solve it exactly grows exponentially as the size of the data set increases. Due to the infeasibility of using algorithms which find all possible solutions, we can use heuristics which are methods used to estimate a solution rapidly. We create a Java program to test seven heuristics on 21 data sets. The seven packing algorithms include four basic greedy algorithms, two backtracking methods, and one random packer. We use data sets from a standard library and create our own data sets with specific characteristics. The greedy algorithm which sorts by largest utility and the one of the backtracking methods perform the best.
Sponsors
Degree Awarded
Bachelor's
Semester
Spring
Department
Mathematics, Engineering & Computer Science