# Find the sum of numbers from an array closest to a number, where repetition of the numbers are allowed

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.

• This problem is NP-hard since it is a generalization of partition. The best you can hope for is a pseudopolynomial-time algorithm. Oct 29, 2019 at 15:56
• 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). Oct 29, 2019 at 16:21
• @Steven How is this a generalization of partition? Can you show it's NP-hard? Oct 30, 2019 at 10:09
• @YuvalFilmus See my answer :) Oct 30, 2019 at 13:01

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$$.

• Thank you for the detailed answer, I am speechless. Oct 31, 2019 at 14:52