2 edited tags
1

# Subset optimization problem

Consider we have a finite set $$S$$ with $$n$$ distinct elements. We want to find a subset $$\{a_1, a_2, \dotsc, a_k\}\subseteq S$$ ($$k\ll n$$) such that a function $$f(a_1,a_2,\dotsc,a_k)$$ is maximized. Consider $$f$$ to be a symmetric function that takes $$k$$ arguments.

More specifically, we are given $$n = 120$$ items, each item being associated with three positive numbers $$(A_i, B_i,C_i)$$, and we want to choose $$k=12$$ items within this set such that

$$\frac{\sum_{k=1}^{12} A_{i_k} \times \left\lceil\frac{\sum_{k=1}^{12} B_{i_k}}{10000}\right\rceil}{\sum_{k=1}^{12} C_{i_k}}$$

is maximal.

If we solve it by exhaustive search it requires $$\binom{120}{12} \approx 10^{16}$$ operations. Is there faster method to this problem? Approximate solution is also fine.