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)?
1 Answer 1
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).