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 .

Implementations

  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 6)
  • Discrete Optimization Methods (Pascal) (rating 4)

    Related Problems

  • Bin Packing
  • Linear Programming

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .