równoważenie wagi szalkowej

Witam,

Proszę o pomoc wy wymyśleniu poprawnego algorytmu do zadania:

Treść
Mamy N odważników o wagach a1, a2, … , aN i wagę, której szalki mogą pomieścić dowolne
liczby odważników. Staramy się umieścić wszystkie odważniki na szalkach tak, aby uzyskać
równowagę. Niestety, nie zawsze jest to możliwe. Na przykład 3 odważników o wagach 1, 4 i
6 nie da się umieścić na szalkach zachowując równowagę. Do przywrócenia równowagi trzeba dodatkowego odważnika b, który należy położyć na lżejszej szalce. W powyższym przykładzie z trzema odważnikami wystarczy dodatkowy ciężar b = 1. W przypadku, gdy dodatkowy odważnik nie jest potrzebny b = 0.
Zadanie
Napisz program, który dla danego zestawu odważników znajdzie najmniejszy ciężar b pozwalający zrównoważyć wagę.

Oto co wymyśliłem

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
        vector<int> tab;
        int L =0;
        int P =0;
        int ileod;
        cin >> ileod;
        while(ileod--)
        {
            int x;
            cin >> x;
            tab.push_back(x);
            
        }

        sort(tab.begin(), tab.end());
        reverse(tab.begin(), tab.end());
        

        L = tab[0];
        P = tab[1];
        for(int i = 2; i < tab.size(); ++i)
        {
            if(P > L)
            {
                L+=tab[i];
            } 
            else
            {
                P += tab[i];
            }
            
        }
        int resz;
        (L>P? resz=L-P:resz=P-L);
        cout << resz << endl;

    system("PAUSE");

    return 0;
}

 

Lecz algorytm nie jest poprawny np dla danych 10 50 60 65 90 90 100 gdzie prawidłową odpowiedzią jest 5, a według mojej metody 35

Przedstawiony przez ciebie problem to wariacja problemu podziału zbioru w wersji optymalizacyjnej ( http://en.wikipedia.org/wiki/Partition_problem ). Pierwszym krokiem, który musisz wykonać jest podział zbioru odważników na dwa podzbiory tak, żeby różnica pomiędzy wagą wszystkich odważników w pierwszym, a wagą wszystkich odważników w drugim zbiorze była jak najmniejsza. Zastosowany przez ciebie sposób (algorytm zachłanny) jest niestety nieprawidłowy (jeżeli chcemy uzyskać wynik optymalny), ponieważ jest to problem NP-trudny, zatem pojedyncza pętla kolejno dodająca ,,odważniki'' w zależności od wagi zbiorów w danej chwili jest niewystarczająca. Poszukaj w internecie lub literaturze sposobów rozwiązania problemu podziału zbioru i zaimplementuj któryś z nich w swoim programie.