It should go for an absolute optimal solution with a greedy twist for ties.
C++0x, compiles on Visual Studio 2010, didn't test with gcc.
Sample output:
C++0x, compiles on Visual Studio 2010, didn't test with gcc.
Sample output:
[ 2 2 3 4 6 7 ] [ 5 8 10 ]
difference = 1
#include <iostream>
#include <set>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct node {
vector<int> left;
vector<int> right;
int sum_left;
int sum_right;
bool operator<(node const & n) const{
return lexicographical_compare(left.begin(), left.end(), n.left.begin(), n.left.end());
}
int diff() const {
return sum_left - sum_right;
}
list<node> neighbours(){
list<node> result;
for(unsigned i = 0; i < left.size(); i++){
if(sum_left - left[i] > sum_right + left[i]){
node cpy(*this);
cpy.left.erase(cpy.left.begin() + i);
cpy.right.insert(lower_bound(cpy.right.begin(), cpy.right.end(), left[i]), left[i]);
cpy.sum_left -= left[i];
cpy.sum_right += left[i];
result.push_back(cpy);
}
}
return result;
}
};
struct node_less_optimal {
bool operator()(node const & a, node const & b){
return a.diff() > b.diff();
}
};
int main(){
int arr[] = {2, 3, 6, 2, 4, 5, 10, 8, 7};
vector<int> v(arr, arr+sizeof(arr)/sizeof(arr[0]));
sort(v.begin(), v.end());
node start;
start.left = v;
int sum = 0; for_each(start.left.begin(), start.left.end(), [&sum](int x){ sum += x;});
start.sum_left = sum;
start.sum_right = 0;
set<node> close;
priority_queue<node, vector<node>, node_less_optimal> open;
open.push(start);
node c;
node optimum = start;
node_less_optimal comp;
while(open.size() > 0){
c = open.top();
if(c.diff() == 0){
optimum = c;
break;
}
close.insert(c);
if(comp(optimum, c))
optimum = c;
open.pop();
auto ns = c.neighbours();
for_each(ns.begin(), ns.end(), [&close, &open](node n){
if(close.find(n)==close.end())
open.push(n);
});
}
cout << "[ ";
for_each(optimum.left.begin(), optimum.left.end(), [](int x){cout << x << " ";});
cout << "] [ ";
for_each(optimum.right.begin(), optimum.right.end(), [](int x){cout << x << " ";});
cout << "]" << endl;
cout << "difference = " << optimum.diff() << endl;
return 0;
}