The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.2.10 Knapsack Problem

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: A set of items S=\{1,...,n\}, where item i has size s_i and value v_i. A knapsack capacity C.

Problem: Find the subset S' \subset S which maximizes the value of \sum_{i \in S'} v_i given that \sum_{i \in S'} s_i \leq C, ie. fits in a knapsack of size C.

Excerpt from The Algorithm Design Manual: 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.


Implementations

  • Silvano Martello and Paolo Toth's Knapsack Problem (FORTRAN) (rating 10)
  • David Pisinger's optimization codes (C) (rating 9)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 5)
  • Discrete Optimization Methods (Pascal) (rating 3)

  • Recommended Books

    Knapsack Problems : Algorithms and Computer Implementations by Silvano Martello and Paolo Toth Knapsack Problems by H. Kellerer and U. Pferschy and P. Pisinger Applied Cryptography : Protocols, Algorithms, and Source Code in C by Bruce Schneier
    Introduction to Algorithms by T. Cormen and C. Leiserson and R. Rivest and C. Stein Introduction to Algorithms by U. Manber Computer Algorithms by S. Baase
    Computers and Intractability: A Guide to the Theory of NP-Completeness by M. R. Garey and D. S. Johnson

    Related Problems


      
    Bin Packing
      
    Linear Programming



    This page last modified on 2008-07-10 .
    www.algorist.com