2
$\begingroup$

I would like to find the sum of values from a given number array, where the repetition of numbers are allowed, closest to a target but the sum cannot exceed the target. If there are more solution, I'd prefer the one with the minimum element count.

Examples:

1)

Given values: [500, 1000, 2000, 5000]

Target: 7000

Result: [2000,5000]

2)

Given values: [500, 1000, 2000, 5000]

Target: 7990

Result: [500, 2000, 5000]

3)

Given values: [222,333]

Target: 444

Result: [222,222]

4)

Given values: [222,333]

Target: 777

Result: [222,222,333]

Later on I would like to implement this algorithm in JavaScript, and make it run in a browser. I have tried:

-Knapsack algorithm

-Generating all combination of the numbers and find one with the minimum difference

but both are very slow when implemented, and used with big numbers.

$\endgroup$
4
  • $\begingroup$ This problem is NP-hard since it is a generalization of partition. The best you can hope for is a pseudopolynomial-time algorithm. $\endgroup$
    – Steven
    Commented Oct 29, 2019 at 15:56
  • $\begingroup$ Your problem is known as the change-making problem if you require the numbers to add up exactly. As noted above, it is weakly NP-hard. If the set of numbers form a matroid, a greedy approach is possible (see greedy solution). $\endgroup$
    – Daniel
    Commented Oct 29, 2019 at 16:21
  • $\begingroup$ @Steven How is this a generalization of partition? Can you show it's NP-hard? $\endgroup$ Commented Oct 30, 2019 at 10:09
  • $\begingroup$ @YuvalFilmus See my answer :) $\endgroup$
    – Steven
    Commented Oct 30, 2019 at 13:01

1 Answer 1

4
$\begingroup$

This problem is NP-hard by a reduction from partition. Let $X = \{x_1, \dots, x_n\}$, be an instance of partition and let $2M = \sum_{x \in X} x$ (assume that $M$ is an integer as otherwise the instance is trivial). Assume that each $x_i$ is positive and let $\ell = \lceil \log 2M \rceil$.

I will now construct some values based on $X$. I will denote a generic value by a tuple $v$ of $n+2$ entries $(v^{*}, v^{(0)}, v^{(1)}, \dots, v^{(n)})$, where all entries $v^{(i)}$, $i=0,\dots,n$ are between $0$ and $2^\ell - 1$. The tuple $v$ will actually correspond to integer whose binary representation is obtained by encoding $v^{*}$ in binary (using a variable number of bits), each of $v^{(0)}, \dots, v^{(n)}$ using $\ell$-bits, and finally concatenating the resulting bitstrings, in order. An example of the tuple $v=(5, 2, 7, 9)$ with $\ell = 4$ is as follows: $$ (\underbrace{101}_{v^*} \underbrace{0010}_{v^{(0)}} \underbrace{0111}_{v^{(1)}} \underbrace{1001}_{v^{(2)}})_2 = (21113)_{10} $$

Notice that the value obtained in this way has an encoding of polynomial length w.r.t. the length of the encoding of the original partition instance, as long as $v^{(*)}$ is small enough (as will be the case). The sum of two tuples is the tuple whose integer value equals the sum of the integer values of the summands.

Let then $y_i = (1, x_i, 0, \dots, 0, 1, 0, \dots, 0)$, where the second entry set to $1$ is $y_i^{(i)}$. Similarly, let $z_i = (1, 0, 0, \dots, 0,1,0, \dots, 0)$, where $z_i^{(i)} = 1$.

The instance of the problem in the question consists of the set of numbers $S = \{y_i : x_i \in X\} \cup \{z_i : x_i \in X\}$ and of the target value $T=(n,M,1, \dots, 1)$.

Given a solution $X' \subseteq X$ to the partition problem, it is easy to construct a solution $S' \subseteq S$ for our problem such that $\sum_{x \in S'} x = T$. Simply select $S' = \{ y_i : x_i \in X'\} \cup \{ z_i : x_i \in X \setminus X' \}$ (notice that it suffices for $S'$ to be a set rather than a multi-set).

I will now argue that if a (multi-)set $S' \subseteq S$ such that $\sum_{x \in S'} x = T$ exists, then the partition instance $X$ has answer "yes". From now on let $S'$ be such a set and notice that, by our choice of $T$, the overall multiplicity of all the elements of $S'$ cannot be larger than $n$ (as otherwise $T^{(*)}$ would be exceeded).

Claim: Let $m(x)$ be multiplicity in $S'$ of $x \in S$. $\forall i=1,\dots,n$ we have $m(y_i) + m(z_i) = 1$.

Proof: If $m(y_i) + m(z_i) = 0$ then, since $T^{(i)}=1$, $S'$ must contain at least $2^\ell \ge 2M > n$ elements $y_j$ or $z_j$ such that $j > i$, contradicting $\sum_{x \in S'} m(x) \le n$.

Assume then that $m(y_i) + m(z_i) > 1$, and consider the tuple $h$ corresponding to the sum of exactly 2 copies of $y_i$ and/or $z_i$ in $S'$. We have $h^{(i)}=2$ and, since $T^{(i)}=1$, we conclude that there must be at least $2^\ell - 2$ other copies of some $y_j$ or $z_j$ for $j \ge i$ in $S'$. The total multiplicity of the elements in $S'$ is therefore at least $2 + 2^\ell - 2 > n$, a contradiction. $\;\; \square$

Let $X' = \{x_i : y_i \in S' \}$ and call $h = \sum_{x \in S'} x$. Since there can be at most one copy of each $z_i$ in $S'$ (see the above Claim), the only way to affect $h^{(0)}$ is through the values $y_i \in S'$. Since there can be at most one copy of each $y_i$ in $S'$ (see the above Claim), we must have $\sum_{x_i \in X'} x_i = \sum_{y_i \in S'} y_i^{(0)} = h^{(0)} = T^{(0)} = M$.

$\endgroup$
1
  • $\begingroup$ Thank you for the detailed answer, I am speechless. $\endgroup$ Commented Oct 31, 2019 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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