# Find combination of elements, one element from each list, whose average is the closest to a target number

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)?

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