# Choosing $n$ points to get the closest sum

Let's say there is a set of $N$ real numbers, $x_i, i\in\{1,2,...,N\}$, and we would like to choose $n$ points out of them to get the sum of the chosen points as close as possible to a certain number, $y$, i.e. minimising $$f(J) = \left[y - \sum_{j\in J}x_j \right]^2 s.t. ~J \subset \{1,2,...,N\} ~\mathrm{and}~ |J| = n$$ To get the exact solution, I think this is an $NP$ problem, so is there any random algorithm to find the (approximate) solution reasonably fast?

• We don't expect randomized algorithms to be able to solve NP-hard problems. – Yuval Filmus Sep 28 '17 at 11:05
• @YuvalFilmus I don't expect it to get the exact solution either. Approximate solution with reasonably low $f$ in a reasonable amount of time is acceptable. – Firman Sep 28 '17 at 11:18
• Round the numbers and then use dynamic programming. ​ ​ – user12859 Sep 28 '17 at 11:20

Round the $x_i$ into multiples of $(\epsilon/n) N$ (for a parameter $\epsilon > 0$ of your choice) which we will denote by $y_i$, and use dynamic programming to solve your problem for the $y_i$ in time $O(n^2N/\epsilon)$, coming up with a set $J$. Since $\sum_{j \in J} |x_j - y_j| \leq \epsilon N$, this will go you the correct answer up to an additive error of $\epsilon N$.