Welcome to the Knapsack

In this collection of modules we examine the very famous Knapsack Problem. For the benefit of readers who have not heard about this OR celebrity, here is a short description of the basic version of the problem, called the Unbounded Knapsack Problem:

We have a knpsack of volume V and n piles (j=1,2,...,n) of items. Each pile contains infinitely many identical items, namely infinitely many items having the same weight (wj) and volume (vj).

The objective is to determine how many items from each pile (xj) should be placed in the knapsack so as to maximize the total weight of the knpsack - obviously without exceeding the total volume of the knapsack (V).

There are numerous other versions to this problem. We shall consider only few.

There are two main OR-based solution methods for this problem, namely branch and bound (BB) and dynamic programming (DP). We consider both.

Contributed by

© The University of Melbourne 1994-2000.
Disclaimer and Copyright Information.
Conditions of use.
Date created: January 15, 2000
Date last modified: February 15, 2000
Authorised by: Moshe Sniedovich
Maintained by: Moshe Sniedovich, Department of Mathematics and Statistics.
Email: m.sniedovich@ms.unimelb.edu.au