- 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 [266].*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 [191].*Garey and Johnson:*MP9