Разбейте набор чисел на две части с наименьшей разницей

Question

Разбейте набор чисел (n чисел) на 2 подмножества так, чтобы сумма чисел в подмножестве 1 имела наименьшую разницу с суммой чисел в подмножестве 2. Также необходимо следующее условие:

• Если n = 2k, каждое подмножество имеет k членов
• Если n = 2k + 1, одно подмножество имеет k членов, а другое - k + 1 членов.

Answer 1

Эта проблема является NP-полной.http://en.wikipedia.org/wiki/Partition_problem Вам придется находить решения с помощью грубой силы.

(Проблема разделения с разделами произвольного размера эквивалентна проблеме с разделами одинакового размера - просто добавьте большое значение C для всехцифры и требуют, чтобы разница была меньше, чем C ...)

Возможно, вы также захотите взглянуть на http://en.wikipedia.org/wiki/Subset_sum_problem

Answer 2

Этот ответ скопирован с http://www.careercup.com/question?id=10244832

Будучи NP-сложным по своей природе, решение относится к алгоритму псевдополиномиального времени со сложностью O (n ^ 2W), где n = количество элементов, W = сумма элементов.

//constraints: n is even
void fun (int items[], int n)
{
    int total = accumulate (items, items+n, 0) / 2;
    int maxSubsetSz = n/2 ;

    vector< vector<int> > T (maxSubsetSz+1, vector<int> (total+1, 0) );

    //T[i][j] is set if there exists subset of size i that sum up to j
    T[0][0] = 1;    

    for(int i = 0; i < n; i++) //consider taking i-th item      
       for(int k = maxSubsetSz-1; k >= 0; k--) //each item must be taken once, hence loop backwards
           for(int j = 0; j <= total-items[i]; j++)  
               if ( T[k][j] && items[i]+j <= total )                        
                     T [k+1] [j+items[i]] = 1;

    for(int j = total; j >= 1; j--)
       if ( T [maxSubsetSz][j] ) {
        cout << "sum : " << j << endl; 
        break;
    }
}

Ответ, предоставленный @hugomg, имеет такую ​​же временную сложность, потому что большое значение C должно быть как минимум равным W (= сумма элементов), поэтому временная сложность задачи о ранце = O (n * (W + nW)) = O (n ^ 2 * W)