Find the smallest group of numbers with sum bigger then $X$

Given a list of numbers $$S$$ where $$0 < s_i < 100$$, find the minimum sum group of numbers with a sum bigger than $$X$$.
Each number can be used multiple times.

Ex: for $$S = [3,4.1], X = 10$$ the solution is $$[3, 3, 4.1]$$

Is it a known problem? What will be the best way of solving it?

For now, my best solution is to randomly pick numbers and repeat the process multiple times.

• Is it possible to assume that the numbers are integers? (For example, if the numbers are rationals, we can transform the problem by multiplying them by a suitable constant, and dropping the constraint $s_i < 100$). Jul 19 '20 at 19:38
• I don't quite understand the question. What's preventing you from selecting $\left\lceil \frac{X}{\max_i s_i} \right\rceil$ copies of $\max_i s_i$? Jul 19 '20 at 20:09
• Sure it does. $\lceil 10/4.1 \rceil = 3$, and your solution uses $3$ elements. Maybe you are not looking for the smallest group of elements with sum at least $X$, but rather for a group of elements with sum $\sigma > X$ that minimizes $\sigma$. Jul 19 '20 at 20:13
• With your conditions, just pick the largest element and repeat it as often as needed. I wouldn't call it a "problem". Jul 20 '20 at 7:14
• “Now it looks NP-complete to me” means it is NP-complete. The special case that all numbers are integers is NP complete. Jul 20 '20 at 13:40

Assuming you are looking for $$S' \subset S$$ with minimal $$\sum_{x \in S'} x > X$$ like Steven suggested, then you should be able to reduce the problem to an instance of knapsack with weights $$w_i$$ and costs $$c_i$$ with $$w_i = c_i = s_i$$ for every $$s_i \in S$$ where the weight of the knapsack is bounded by $$X$$.

If the solution $$K := \sum_{x \in S'} x$$ is not greater than $$X$$, you need to repeat the process by setting $$X := X + \varepsilon$$ where $$\varepsilon$$ is the minimal distance between any two subset sums of $$S$$ and running knapsack again until it yields a solution $$K > X$$.

Edit: Turns out that finding $$\varepsilon$$ isn't an easy problem. I first assumed $$\varepsilon$$ is the minimum between any two numbers in $$S$$, which can be found by sorting the list and finding the minimum between two adjacent elements. This would yield a good approximation in most cases, but it might not be the optimal solution. If your problem statement uses $$\geq$$ instead of $$>$$, transforming the problem into knapsack will yield an optimal solution, no repetitions required.

• Yeah, I agree. It is a special case of knapsack problem where weights equal to costs. The problem is that I can't use a DP to solve this as I deal with real numbers. Don't have enough memory to convert them to integers. Jul 20 '20 at 1:56

Let me assume that all involved numbers are positive integers and let $$n=|S|$$. From the comments to your question, I understand your problem as follows:

Given a set $$S = \{s_1, \dots, S_n\}$$ find a multiset $$S'$$ such that (i) each element of $$S'$$ belongs to $$S$$,( ii) the sum $$\sigma$$ of the elements in $$S'$$ is larger than $$X$$, and (iii) $$S'$$ minimizes $$\sigma$$.

You can solve the above problem in time $$O(nX)$$ with a dynamic programming algorithm.

For an integer $$w < X$$, let $$OPT[w]$$ be true ($$\top$$) if it is possible to select a group of numbers with a total sum of $$w$$, and false ($$\bot$$) otherwise.

For $$w < 0$$ we have $$OPT[w] = \bot$$. Moreover $$OPT[0]= \top$$ and, for $$w>0$$: $$OPT[w] = \bigvee_{i=1,\dots,n} OPT[w-s_i].$$

The minimum attainable sum $$\sigma$$ that is larger than $$X$$ is then: $$\min_{i=1,\dots,n} \min_{\substack{j = X-s_i+1, \dots, X \\ OPT[j]=\top}} (j+s_i).$$

The actual group of numbers that sum to $$\sigma$$ can be found by retracing (backwards) the dynamic programming choices.

If each number can be selected once, it is exactly the knapsack problem (known to be NP-complete): Just turn it on its head, and ask for the numbers left out, they are the set with the largest sum less than $$S - X$$, where $$S$$ is the sum of all numbers. Exactly the knapsack problem.

• Are there known algorithms for solving the knapsack problem with big integer values as a weight? Jul 20 '20 at 17:55