This is the 0-1 quadratic knapsack problem, which is NP-hard. The binary decision variables $x_i$ indicate whether $i\in S$, and the knapsack capacity is $k$.
RobPratt
- 5.4k
- 1
- 15
- 25