0
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ 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$). $\endgroup$
    – Steven
    Jul 19 '20 at 19:38
  • 3
    $\begingroup$ 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$? $\endgroup$
    – Steven
    Jul 19 '20 at 20:09
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Steven
    Jul 19 '20 at 20:13
  • 1
    $\begingroup$ With your conditions, just pick the largest element and repeat it as often as needed. I wouldn't call it a "problem". $\endgroup$
    – gnasher729
    Jul 20 '20 at 7:14
  • 1
    $\begingroup$ “Now it looks NP-complete to me” means it is NP-complete. The special case that all numbers are integers is NP complete. $\endgroup$
    – gnasher729
    Jul 20 '20 at 13:40
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jul 20 '20 at 1:56
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.