##
1.2.10 Knapsack Problem

##
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
.