Разложить камни на 2 кучки так, чтобы разница масс этих кучек была минимальной.

int solve(int* a, int N){
int s=0;
int i;
for (i=0; i<N; i++)
 s+=a[i];
int* t1, t2, t3;
int sz=s/2+s%2;
int* t1=new int[sz+1];
int* t2=new int[sz+1];
for (i=0; i<sz; i++)
{
    t1[sz]=0; t2[sz]=0;
}
for (i=0; i<N; i++){
 for (j=0; j<=sz; j++){
    if (j-a[i]>=0){
         t2[j]=max(t1[j], t1[j-a[i]]+a[i]);
       }
       else
         t2[j]=t1[j];
  }
t3=t2;
t2=t1;
t1=t3;
}
delete[] t1;
delete[] t2;
 
 
int a, dsz, c;
a=s-t2[sz];
if (a>t2[sz]) dsz=a-t2[sz];
else dsz=t2[sz]-a;
a=s-t2[sz-1];
if (a>t2[sz-1]) c=a-t2[sz];
else c=t2[sz]-a;
 
if (dsz<c) return dsz;
else return c 
}

#include <iostream>
 
 
using namespace std;
 
int main()
{
int a,t;
cin>>a;
int b[19];
for (int i=0;i<a;i++) {cin>>b[i];}
if (a!=1) {
for (int y=0;y<a;y++){
    for (int h=y+1;h<a;h++) {
        if (b[y]>b[h])
         {t=b[y];
         b[y]=b[h];
         b[h]=t;
         }
         }
         }
 
 int s1=b[a-1];
 
 int s2=b[a-2];
  
 int k=a-3;
 
  while (k>(-1)) {
        if (s1>s2) { s2+=b[k];} else {s1+=b[k];}
        
        k--;
}
 
int u=s1-s2;
if (u>0) {cout<<u;} else {cout<<-u;};}
 
      else {cout<<b[0];};
         
 
 
 
 
    return 0;
}

class heaps
{
public:
    heaps(double *, int);
    ~heaps();
    static void print();
private:
    heaps(vector<double> *, vector<double> *, vector<double> *);
    static bool goldHit;
    static double bestDiff;
    static double halfWeight;
    static vector<double> bestFirstHeap;
    static vector<double> bestSecondHeap;
    vector<double> * restHeapPtr;
    vector<double> * firstHeapPtr;
    vector<double> * secondHeapPtr;
    void firstPart();
    void secondPart();
    void initiate();
};

#include "stdafx.h"
 
#include <iostream>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <iterator>
#include <numeric>
 
#include "Heaps.h"
 
bool heaps::goldHit = false;
double heaps::bestDiff = 0.0;
double heaps::halfWeight = 0.0;
vector<double> heaps::bestFirstHeap = vector<double>();
vector<double> heaps::bestSecondHeap = vector<double>();
 
heaps::heaps(double * stoneArray, int arrSize)
{
    sort(stoneArray, stoneArray + arrSize);
    halfWeight = accumulate(stoneArray, stoneArray + arrSize, 0.0) / 2.0;
    restHeapPtr = new vector<double>(stoneArray, stoneArray + arrSize);
    firstHeapPtr = new vector<double>();
    secondHeapPtr = new vector<double>();
    secondHeapPtr->push_back(restHeapPtr->back());
    restHeapPtr->pop_back();
    bestFirstHeap = *restHeapPtr;
    bestSecondHeap = *secondHeapPtr;
    if (bestSecondHeap.back() == halfWeight)
        goldHit = true;
    else
    {
        bestDiff = fabs(accumulate(bestFirstHeap.begin(), bestFirstHeap.end(), 0.0) - accumulate(bestSecondHeap.begin(), bestSecondHeap.end(), 0.0));
        initiate();
    }
}
 
heaps::heaps(vector<double> * rest, vector<double> * first, vector<double> * second)
{
    restHeapPtr = new vector<double>(*rest);
    firstHeapPtr = new vector<double>(*first);
    secondHeapPtr = new vector<double>(*second);
}
 
heaps::~heaps()
{
    delete secondHeapPtr;
    secondHeapPtr = nullptr;
    delete firstHeapPtr;
    firstHeapPtr = nullptr;
    delete restHeapPtr;
    restHeapPtr = nullptr;
}
 
void heaps::firstPart()
{
    if (goldHit)
        return;
    assert(restHeapPtr->size() > 3);
    bool heapsStateChanged = true;
    bool firstHeapChanged = false;
    bool secondHeapChanged = false;
    double weight1 = accumulate(firstHeapPtr->begin(), firstHeapPtr->end(), 0.0);
    
    double weight2 = accumulate(secondHeapPtr->begin(), secondHeapPtr->end(), 0.0);
    vector<double>::const_iterator pos;
    do
    {
        for (pos = restHeapPtr->cbegin(); pos != restHeapPtr->cend(); ++pos)
        {
            if (*pos + weight2 == halfWeight)
            {
                goldHit = true;
                secondHeapPtr->push_back(*pos);
                restHeapPtr->erase(pos);
                copy(restHeapPtr->cbegin(), restHeapPtr->cend(), back_inserter(*firstHeapPtr));
                bestFirstHeap = *firstHeapPtr;
                bestSecondHeap = *secondHeapPtr;
                bestDiff = 0;
                delete this;
                return;
            }
            else if (*pos + weight2 > halfWeight)
                break;
        }
        if (pos != restHeapPtr->cend() && ++pos != restHeapPtr->cend())
        {
            copy(pos, restHeapPtr->cend(), back_inserter(*secondHeapPtr));
            restHeapPtr->erase(pos, restHeapPtr->cend());
            firstHeapChanged = true;
            if (restHeapPtr->size() <= 3)
            {
                while (restHeapPtr->size() != 3)
                {
                    restHeapPtr->push_back(secondHeapPtr->back());
                    secondHeapPtr->pop_back();
                }
                secondPart();
                return;
            }
        }
        else
            firstHeapChanged = false;
        for (pos = restHeapPtr->cbegin(); pos != restHeapPtr->cend(); ++pos)
        {
            if (*pos + weight1 == halfWeight)
            {
                goldHit = true;
                firstHeapPtr->push_back(*pos);
                restHeapPtr->erase(pos);
                copy(restHeapPtr->cbegin(), restHeapPtr->cend(), back_inserter(*secondHeapPtr));
                bestFirstHeap = *firstHeapPtr;
                bestSecondHeap = *secondHeapPtr;
                bestDiff = 0;
                delete this;
                return;
            }
            else if (*pos + weight1 > halfWeight)
                break;
        }
        if (pos != restHeapPtr->cend() && ++pos != restHeapPtr->cend())
        {
            copy(pos, restHeapPtr->cend(), back_inserter(*firstHeapPtr));
            restHeapPtr->erase(pos, restHeapPtr->cend());
            secondHeapChanged = true;
            if (restHeapPtr->size() <= 3)
            {
                while (restHeapPtr->size() != 3)
                {
                    restHeapPtr->push_back(firstHeapPtr->back());
                    firstHeapPtr->pop_back();
                }
                secondPart();
                return;
            }
        }
        else
            secondHeapChanged = false;
        heapsStateChanged = firstHeapChanged || secondHeapChanged;
        firstHeapChanged = false;
        secondHeapChanged = false;
    }while (heapsStateChanged);
 
    
    double tempDouble = restHeapPtr->back();
    restHeapPtr->pop_back();
    secondHeapPtr->push_back(tempDouble);
    heaps * tempHeaps1 = new heaps(restHeapPtr, firstHeapPtr, secondHeapPtr);
    secondHeapPtr->pop_back();
    firstHeapPtr->push_back(tempDouble);
    heaps * tempHeaps2 = new heaps(restHeapPtr, firstHeapPtr, secondHeapPtr);
    tempHeaps1->initiate();
    if (goldHit)
        return;
    else
        tempHeaps2->initiate();
    delete this;
}
 
void heaps::secondPart()
{
    if (goldHit)
        return;
    double thisDiff, tempDiff;
    int bestCase;
    assert(restHeapPtr->size() == 3);
    double weight1 = accumulate(firstHeapPtr->begin(), firstHeapPtr->end(), 0.0);
    double weight2 = accumulate(secondHeapPtr->begin(), secondHeapPtr->end(), 0.0);
    bestCase = 1; //первый камень из оставшихся идет в первую кучу
    thisDiff = fabs(weight1 + restHeapPtr->at(0) - weight2 - restHeapPtr->at(1) - restHeapPtr->at(2));
    if (thisDiff == 0)
    {
        goldHit = true;
        bestFirstHeap = *firstHeapPtr;
        bestFirstHeap.push_back(restHeapPtr->at(0));
        bestSecondHeap = *secondHeapPtr;
        bestSecondHeap.push_back(restHeapPtr->at(1));
        bestSecondHeap.push_back(restHeapPtr->at(2));
        bestDiff = 0.0;
        delete this;
        return;
    }
    tempDiff = fabs(weight1 + restHeapPtr->at(1) - weight2 - restHeapPtr->at(0) - restHeapPtr->at(2));
    if (tempDiff == 0)
    {
        goldHit = true;
        bestFirstHeap = *firstHeapPtr;
        bestFirstHeap.push_back(restHeapPtr->at(1));
        bestSecondHeap = *secondHeapPtr;
        bestSecondHeap.push_back(restHeapPtr->at(0));
        bestSecondHeap.push_back(restHeapPtr->at(2));
        bestDiff = 0.0;
        delete this;
        return;
    }
    else if (tempDiff < thisDiff)
    {
        thisDiff = tempDiff;
        bestCase = 2; //второй камень из оставшихся идет в первую кучу
    }
    tempDiff = fabs(weight1 + restHeapPtr->at(2) - weight2 - restHeapPtr->at(0) - restHeapPtr->at(1));
    if (tempDiff == 0)
    {
        goldHit = true;
        bestFirstHeap = *firstHeapPtr;
        bestFirstHeap.push_back(restHeapPtr->at(2));
        bestSecondHeap = *secondHeapPtr;
        bestSecondHeap.push_back(restHeapPtr->at(0));
        bestSecondHeap.push_back(restHeapPtr->at(1));
        bestDiff = 0.0;
        delete this;
        return;
    }
    else if (tempDiff < thisDiff)
    {
        thisDiff = tempDiff;
        bestCase = 3; //третий камень из оставшихся идет в первую кучу
    }
    tempDiff = fabs(weight2 + restHeapPtr->at(0) - weight1 - restHeapPtr->at(1) - restHeapPtr->at(2));
    if (tempDiff == 0)
    {
        goldHit = true;
        bestFirstHeap = *firstHeapPtr;
        bestFirstHeap.push_back(restHeapPtr->at(1));
        bestFirstHeap.push_back(restHeapPtr->at(2));
        bestSecondHeap = *secondHeapPtr;
        bestSecondHeap.push_back(restHeapPtr->at(0));
        bestDiff = 0.0;
        delete this;
        return;
    }
    else if (tempDiff < thisDiff)
    {
        thisDiff = tempDiff;
        bestCase = 4; //первый камень из оставшихся идет во вторую кучу
    }
    tempDiff = fabs(weight2 + restHeapPtr->at(1) - weight1 - restHeapPtr->at(0) - restHeapPtr->at(2));
    if (tempDiff == 0)
    {
        goldHit = true;
        bestFirstHeap = *firstHeapPtr;
        bestFirstHeap.push_back(restHeapPtr->at(0));
        bestFirstHeap.push_back(restHeapPtr->at(2));
        bestSecondHeap = *secondHeapPtr;
        bestSecondHeap.push_back(restHeapPtr->at(1));
        bestDiff = 0.0;
        delete this;
        return;
    }
    else if (tempDiff < thisDiff)
    {
        thisDiff = tempDiff;
        bestCase = 5; //второй камень из оставшихся идет во вторую кучу
    }
    tempDiff = fabs(weight2 + restHeapPtr->at(2) - weight1 - restHeapPtr->at(0) - restHeapPtr->at(1));
    if (tempDiff == 0)
    {
        goldHit = true;
        bestFirstHeap = *firstHeapPtr;
        bestFirstHeap.push_back(restHeapPtr->at(0));
        bestFirstHeap.push_back(restHeapPtr->at(1));
        bestSecondHeap = *secondHeapPtr;
        bestSecondHeap.push_back(restHeapPtr->at(2));
        bestDiff = 0.0;
        delete this;
        return;
    }
    else if (tempDiff < thisDiff)
    {
        thisDiff = tempDiff;
        bestCase = 6; //третий камень из оставшихся идет во вторую кучу
    }
    tempDiff = fabs(weight1 + restHeapPtr->at(0) + restHeapPtr->at(1) + restHeapPtr->at(2) - weight2);
    if (tempDiff == 0)
    {
        goldHit = true;
        bestFirstHeap = *firstHeapPtr;
        bestFirstHeap.push_back(restHeapPtr->at(0));
        bestFirstHeap.push_back(restHeapPtr->at(1));
        bestFirstHeap.push_back(restHeapPtr->at(2));
        bestSecondHeap = *secondHeapPtr;
        bestDiff = 0.0;
        delete this;
        return;
    }
    else if (tempDiff < thisDiff)
    {
        thisDiff = tempDiff;
        bestCase = 7; //все оставшиеся камни попадают в первую кучу
    }
    tempDiff = fabs(weight2 + restHeapPtr->at(0) + restHeapPtr->at(1) + restHeapPtr->at(2) - weight1);
    if (tempDiff == 0)
    {
        goldHit = true;
        bestFirstHeap = *firstHeapPtr;
        bestSecondHeap = *secondHeapPtr;
        bestSecondHeap.push_back(restHeapPtr->at(0));
        bestSecondHeap.push_back(restHeapPtr->at(1));
        bestSecondHeap.push_back(restHeapPtr->at(2));
        bestDiff = 0.0;
        delete this;
        return;
    }
    else if (tempDiff < thisDiff)
    {
        thisDiff = tempDiff;
        bestCase = 8; //все оставшиеся камни попадают во вторую кучу
    }
    if (thisDiff < bestDiff)
    {
        bestFirstHeap = *firstHeapPtr;
        bestSecondHeap = *secondHeapPtr;
        bestDiff = thisDiff;
        switch (bestCase)
        {
            case 1:
                bestFirstHeap.push_back(restHeapPtr->at(0));
                bestSecondHeap.push_back(restHeapPtr->at(1));
                bestSecondHeap.push_back(restHeapPtr->at(2));
                break;
            case 2:
                bestFirstHeap.push_back(restHeapPtr->at(1));
                bestSecondHeap.push_back(restHeapPtr->at(0));
                bestSecondHeap.push_back(restHeapPtr->at(2));
                break;
            case 3:
                bestFirstHeap.push_back(restHeapPtr->at(2));
                bestSecondHeap.push_back(restHeapPtr->at(0));
                bestSecondHeap.push_back(restHeapPtr->at(1));
                break;
            case 4:
                bestFirstHeap.push_back(restHeapPtr->at(1));
                bestFirstHeap.push_back(restHeapPtr->at(2));
                bestSecondHeap.push_back(restHeapPtr->at(0));
                break;
            case 5:
                bestFirstHeap.push_back(restHeapPtr->at(0));
                bestFirstHeap.push_back(restHeapPtr->at(2));
                bestSecondHeap.push_back(restHeapPtr->at(1));
                break;
            case 6:
                bestFirstHeap.push_back(restHeapPtr->at(0));
                bestFirstHeap.push_back(restHeapPtr->at(1));
                bestSecondHeap.push_back(restHeapPtr->at(2));
                break;
            case 7:
                bestFirstHeap.push_back(restHeapPtr->at(0));
                bestFirstHeap.push_back(restHeapPtr->at(1));
                bestFirstHeap.push_back(restHeapPtr->at(2));
                break;
            case 8:
                bestSecondHeap.push_back(restHeapPtr->at(0));
                bestSecondHeap.push_back(restHeapPtr->at(1));
                bestSecondHeap.push_back(restHeapPtr->at(2));
                break;
        }
    }
    delete this;
}
 
void heaps::initiate()
{
    if (restHeapPtr->size() > 3)
        firstPart();
    else
        secondPart();
}
 
void heaps::print()
{
    sort(bestFirstHeap.begin(), bestFirstHeap.end());
    sort(bestSecondHeap.begin(), bestSecondHeap.end());
    cout << "Best stone distribution is as follows: " << endl;
    cout << "Heap 1: ";
    copy (bestFirstHeap.begin(), bestFirstHeap.end(), ostream_iterator<double>(cout, ", "));
    cout << "\b\b  " << endl;
    cout << "Heap 2: ";
    copy (bestSecondHeap.begin(), bestSecondHeap.end(), ostream_iterator<double>(cout, ", "));
    cout << "\b\b  " << endl;
    cout << "Weights differense is " << bestDiff << endl;
}

#include "stdafx.h"
#include <iostream>
#include <cassert>
#include <vector>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <cmath>
 
#include "Heaps.h"
 
using namespace std;
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    double stoneArray[] = {21, 2, 7, 4, 7, 3, 3, 10, 10, 18, 19, 10};
    
 
    assert(sizeof(stoneArray) / sizeof(stoneArray[0]) > 1);
    if (sizeof(stoneArray) <= 3) //неинтересный случай, решаемый вручную
    {
        sort(stoneArray, stoneArray + sizeof(stoneArray) / sizeof(stoneArray[0]));
        cout << "Best stone distribution is as follows: " << endl;
        cout << "Heap 1: ";
        copy (stoneArray, stoneArray + sizeof(stoneArray) / sizeof(stoneArray[0]) - 1, ostream_iterator<double>(cout, ", "));
        cout << "\b\b  " << endl;
        cout << "Heap 2: ";
        cout << stoneArray[sizeof(stoneArray) / sizeof(stoneArray[0]) - 1];
        cout << endl;
        cout << "Weights differense is " << fabs(accumulate(stoneArray, stoneArray + sizeof(stoneArray) / sizeof(stoneArray[0]) - 1, 0.0) - stoneArray[sizeof(stoneArray) / sizeof(stoneArray[0]) - 1]) << endl;
    }
    else //а здесь с использованием класса
    {
        heaps * MyHeapsPtr = new heaps(stoneArray, sizeof(stoneArray) / sizeof(stoneArray[0]));
        MyHeapsPtr->print();
        //delete MyHeapsPtr; не требуется ибо удаляется в функции SecondPart()
    }
    cout << endl;
    return 0;
}