0

Given a collection $S$ with up to $1,000,000$ values where $0 < S_i < 100$. I need to find the top $k$ groups whose sum is bigger than $N$ where $0 < k < 1,000$ and $N$ is a big positive number. The groups are sub-collections of $S$ where duplicates are allowed.

Ex: for $S=[1.1,3], k = 2, N=4$ the solution is:

  • $[1.1, 3] \rightarrow 4.1$
  • $[1.1, 1.1, 1.1, 1.1] \rightarrow 4.4$

I am not sure how to approach this, I been trying to sort $S$ from small to big, then start with a group made of $S_1$, then replace one of the variables with $s_2$ and remove as many $S_1$ as I can, repeat the process until I got no $S_1$ in the group and continue with $S_2$. But this don't cover all the cases. And it's a very slow method.

halrankard
  • 3,454
Ilya Gazman
  • 1,440
  • This is not clear. In your example, does $S$ consist of the two values $1.1$ and $9$ or all the real numbers between $1.1$ and $9$? In either case, what's special about the two examples you mentioned? Why not just use ${9}$? Or ${1.1, 4}$? Or.... – lulu Jul 19 '20 at 14:01
  • @lulu sorry, had a typo, I updated it – Ilya Gazman Jul 19 '20 at 15:21
  • Still not clear. What does "the top $k$" mean? How are you ranking these? – lulu Jul 19 '20 at 15:28
  • @lulu between-group $a$ and $b$ the one with the smaller sum of elements should be ranked higher. The sum of the elements in the group must be above $N$ – Ilya Gazman Jul 19 '20 at 16:13

1 Answers1

1

Found a probabilistic solution that cover all the cases.

Pick values in random from $S$ until the sum is above $N$. Repeat the process multiple times while kipping the top $k$ best results.

I hope others will be able to find a better solution.

Ilya Gazman
  • 1,440