Next: MAXIMUM INTEGER M-DIMENSIONAL KNAPSACK Up: Mathematical Programming Previous: MAXIMUM HYPERPLANE CONSISTENCY Index

### MAXIMUM KNAPSACK

- 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