MP13 M AXIMUM K NAPSACK

     
• I NSTANCE : Finite set U , for each a size and a value , a positive integer .
• S OLUTION : A subset such that .
• M EASURE : Total weight of the chosen elements, i.e., .

• Good News: Admits an FPTAS [ 184 ].
• 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 [ 129 ].
• Garey and Johnson: MP9