Addition of 4 terms closest to Pi [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question appears to be off-topic because it lacks sufficient information to diagnose the problem. Describe your problem in more detail or include a minimal example in the question itself.

Closed 9 years ago.

Improve this 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.

Answer 2

You could sort the list of items, which requires O(n log(n) ) time. Then, given a+b+c, you can find the best d using binary search.

You could also (possibly, depending on the data) cut the search tree by checking if the partial sum at any step is too large or too small to have a chance of becoming the correct solution.

By taking these two steps you should be able to reduce the runtime drastically.

Answer 3

I suggest you to use Genetic Algorithms with these settings :

Chromosome : [a,b,c,d]

Fitness function: |f₁₀₀₀₀(a) + f₁₀₀₀₀(b) + f₁₀₀₀₀(c) + f₁₀₀₀₀(d) - π|

Crossover (Ch1,Ch2): Xover([a,b,c,d],[a',b',c',d']) -> [a,b,c',d'] , [a',b',c,d] *

Mutation (Ch) : Mutate([a,b,c,d]) -> [a,b',c,d] **

This problem is really easy for GA to solve and if you implement it you will find it solves the problem in a short time.
* Choose the crossover point randomly

** Replace one of the genes in the chromosome (randomly selected) with one of the possible points

Note that in this post I just gave the key points, however if you are not familiar with the GA at all, you could read about the whole topic and I will help you for more details.