Heuristics for the Knapsack Problem

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.