next up previous contents index CD CD Algorithms
Next: Discrete Fourier Transform Up: Numerical Problems Previous: Arbitrary-Precision Arithmetic

Knapsack Problem



Input description: A set of items tex2html_wrap_inline27600 , where item i has size tex2html_wrap_inline27602 and value tex2html_wrap_inline27604 . A knapsack capacity C.

Problem description: Find the subset tex2html_wrap_inline27606 that maximizes the value of tex2html_wrap_inline27608 given that tex2html_wrap_inline27610 ; i.e. all the items fit in a knapsack of size C.

Discussion: The knapsack problem arises whenever there is resource allocation with financial constraints. Given a fixed budget, how do you select what things you should buy. Everything has a cost and value, so we seek the most value for a given cost.   The term knapsack problem invokes the image of the backbacker who is constrained by a fixed-size knapsack and so must fill it only with the most useful items.    

The typical formulation in practice is the 0/1 knapsack problem,   where each item must be put entirely in the knapsack or not included at all. Objects cannot be broken up arbitrarily, so its not fair taking one can of coke from a six-pack or opening the can to take just a sip. It is this 0/1 property that makes the knapsack problem hard, for a simple greedy algorithm finds the optimal selection whenever we are allowed to subdivide objects arbitrarily.   For each item, we could compute its ``price per pound'', and take as much of the most expensive item until we have it all or the knapsack is full. Repeat with the next most expensive item, until the knapsack is full. Unfortunately, this 0/1 constraint is usually inherent in most applications.

Issues that arise in selecting the best algorithm include:

When the knapsack capacity gets too large for dynamic programming, exact solutions can be found using integer programming or backtracking.     A 0/1 integer variable tex2html_wrap_inline27668 is used to denote whether item i is present in the optimal subset. We maximize tex2html_wrap_inline27670 given the constraint that tex2html_wrap_inline27672 . Algorithms and implementations of integer and linear programming are discussed in Section gif.

When exact solutions prove too costly to compute, heuristics should be used. The simple greedy heuristic inserts items according to the maximum `price per pound' rule, described above.   Often this heuristic solution is close to optimal, but it can be arbitrarily bad depending upon the problem instance. The ``price per pound'' rule can also be used to reduce the size of the problem instance in exhaustive search-based algorithms by eliminating ``cheap but heavy'' objects from future consideration.

Another heuristic is based on scaling.   Dynamic programming works well if the capacity of the knapsack is a reasonably small integer, say tex2html_wrap_inline27674 . But what if we have a problem with capacity tex2html_wrap_inline27676 ? We scale down the sizes of all items by a factor of tex2html_wrap_inline27678 , round the size down to an integer, and then use dynamic programming on the scaled items. Scaling works well in practice, especially when the range of sizes of items is not too large.

Implementations: Martello and Toth's book [MT90a] comes with a disk of Fortran implementations of a variety of knapsack algorithms.   This is likely the best source of code currently available.

Algorithm 632 [MT85] of the Collected Algorithms of the ACM is a Fortran code for the 0/1 knapsack problem, with the twist that it supports multiple knapsacks.   See Section gif.

Pascal implementations of several knapsack algorithms, including backtracking and a refined greedy algorithm, are provided in [SDK83]. See Section gif for details.  

Notes: Martello and Toth's book [MT90a] and survey article [MT87] are the standard references on the knapsack problem, including most theoretical and experimental results. An excellent exposition on integer programming approaches to knapsack problems appears in [SDK83]. See [FP75a] for a computational study of algorithms for 0-1 knapsack problems.

A polynomial-time approximation scheme is an algorithm that approximates the optimal solution of a problem in time polynomial in both its size and the approximation factor tex2html_wrap_inline27680 .     This very strong condition implies a smooth tradeoff between running time and approximation quality. Good expositions on the polynomial-time approximation scheme [IK75] for knapsack and subset sum includes [Baa88, CLR90, GJ79, Man89].

The first algorithm for generalized public key encryption by Merkle   and Hellman [MH78] was based on the hardness of the knapsack problem. See [Sch94] for an exposition.

Related Problems: Bin packing (see page gif), integer programming (see page gif).    

next up previous contents index CD CD Algorithms
Next: Discrete Fourier Transform Up: Numerical Problems Previous: Arbitrary-Precision Arithmetic

Mon Jun 2 23:33:50 EDT 1997