Algorithm to separate a vector into two others

Hello !

I have a question.
I need to make an algorithm to separate a vector of 2*n ints into two vector of n ints, but the sum of both vectors (absolute) must be the lowest.

Example :

Code:

---

The "big" vector : 1000 2 3 4 5 6 7 2000
n = 4
The two vectors must be :
- 2000 2 3 4 ; sum = 2009
- 1000 5 6 7 ; sum = 1018
abs(2009 - 1018) = 991  (which is the lowest)

---

I searched all the web to find an algorithm like this, but i didn't found it.


If you can help me, it would be very nice :)

I am still trying to wrap my head around your question... What? Are you just arbitrarily splitting up a large vector or is there some rationale behind how it is split?

This is a variant of the Partitioning Problem. In this case you're looking for the closest approximation to the exact partition.

First I thinked it was a partitioning problem.
But, in the partitoning problem, you don't have two vectors of the same size...

But perhaps you can modify an algorithm that solves the Partitioning Problem to suit your current problem?

Yes, I think it is what I will do.
If it don't work, I will find the algorithm alone... (I began, but it isn't very optimizated)