Addition of 4 terms closest to Pi

Question

I have the following mathematical and proggramming problem: I have a list of about 14000 items. I must chose 4 items so that a + b + c + d - pi = minimal error

going threw all options will take far too long time. I am supposed to build a program (i'm doing it with a python script) that will solve this problem

Any ideas?

Edit: If it helps, the items are e^k/10000 - 1 for every k between 0 and about 14400 (that will give pi)

Answer 1

This is a variation of Subset Sum Problem with fixed subset size. (You are facing the optimization problem).
The existence solution (Is there a subset that sums exactly to pi) is discussed thoroughly in the thread: Sum-subset with a fixed subset size.

In your problem (the optimization problem) - if you can repeat an element more than once - it is easily solveable in O(n²log) with O(n²) additional space as follows:

1. Create an array of size O(n²) containing all possible sum of pairs. Let it be arr.
2. Sort arr - O(n^2logn)
3. For each element e of arr - binary search in arr to find the element closest to pi-e.
4. Yield the two pairs that got the best result in step 3.

The complexity of step 3 is O(logn) per iteration, and n² iterations - so O(n^2logn) total.