Next: MAXIMUM INTEGER M-DIMENSIONAL KNAPSACK
Up: Mathematical Programming
Previous: MAXIMUM HYPERPLANE CONSISTENCY
  Index
- INSTANCE:
Finite set U, for each
a size
and a value
,
a positive integer
.
- SOLUTION:
A subset
such that
.
- MEASURE:
Total weight of the chosen elements, i.e.,
.
- Good News:
Admits an FPTAS [251].
- Comment:
The special case when s(u)=v(u) for all
is called
MAXIMUM SUBSET SUM.
The corresponding minimization problem where
also admits an FPTAS, as well as
several other variations of the knapsack problem [179].
- Garey and Johnson: MP9
Viggo Kann
1999-04-22