0
$\begingroup$

Problem:

There are L lists of positive integers, say L_0, L_1, L_2 ... L_|L|-1.

The lists have equal length.

There is a target number T.

Find what is the combination of elements, one element from each list, whose average is the closest to T.

Example:

L_0 = [10, 20, 15]
L_1 = [9000, 400, 550]
L_2 = [1, 2, 3]
L_3 = [700, 500, 1000]
T = 3000

The combination of elements, one element from each list, whose average is the closest to 3000 is: 20, 9000, 3, 1000.

Question:

Is there a better way to solve this problem than just bruteforce (testing all possible combinations)?

$\endgroup$

1 Answer 1

1
$\begingroup$

The problem is NP-Hard by a reduction from subset sum. Let $X = \{x_1, x_2, \dots, x_n\}$ be a set of integers and let $t$ be an integer. The subset-sum problem asks whether there is a subset $S \subseteq X$ such that $\sum_{x \in S} x = t$.

To reduce to your problem pick $L=n$, $L_i = [0, x_i]$, and $T = \frac{T}{n}$. There is a solution to the subset sum instance if and only if there is a way to choose an item from each list such that their average is exactly $T$.

If you are willing to settle for a pseudopolynomial-time algorithm then you can use dynamic programming. Assume $T \ge 1$ (otherwise the solution is trivial). Let $OPT[t,ji]$ be true ($\top$) if there is a way to choose one element from each of $L_1, \dots, L_i$ so that the sum of the chosen elements is $t$, and false ($\bot$) otherwise.

Then, $OPT[t,0] = \top$ if and only if $t=0$. For $i = 1 \dots, n$ and $t=1,\dots, \lceil nT \rceil$: $$ OPT[t,i] = \bigvee_{x \in L_i} OPT[t-x, i-1] $$

You can compute all $OPT[t,i]$ in time $O(n^2T)$. Then the absolute difference between the average best choice of elements and $T$ is: $$ \min_{\substack{t=0, \dots, \lceil nT \rceil \\ OPT[t,n]=\top} } \left| \frac{t}{n} - T \right|. $$ The actual choice of elements can be found with standard techniques (e.g., whenever $OPT[i,t]=\top$ keep track of an element $x \in L_i$ such that $OPT[t-x, i-1] = \top$ and trace back the optimal choices from $OPT[t^*, n]$, where $t^*$ is a value of $t$ that attains the above minimum).

$\endgroup$

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.