минимальная разница между суммой двух подмножеств

Question

Folks,

столкнулся с проблемой ... нашел межжала ... я модифицируя его немного только ту зажигательную его.

Учитывая набор целых чисел (диапазон 0-500), найдите минимальную разницу между суммой двух подмножеств, которые могут быть сформированы путем их разбиения почти одинаково. (скажем, число целых чисел равно n, если n четно, каждое множество должно иметь n/2 элементов, а если n нечетно, то в одном наборе есть (n-1)/2 элементов, а у другого есть (n + 1)/2 элемента)

образца Imput: 1 2 3 4 5 6

минимальная разница = 1 (подмножеств равно 1 4 6 и 2 3 5)

входной образец 2: [1 1 1 1 2 2 2 2]

минимальная разница = 0 (подмножеств равно 1 1 2 2 и 1 1 2 2)

- это подход DP для этой проблемы.

Спасибо, ребята ...

Raj ...

Answer 1

from random import uniform 
    l=[int(uniform(0, 500)) for x in xrange(15)] 
    l.sort() 
    a=[] 
    b=[] 
    a.append(l.pop()) 
    while l: 
     if len(a) > len(b): 
      b.append(l.pop()) 
     elif len(b) > len(a): 
      a.append(l.pop()) 
     elif sum(a) > sum(b): 
      b.append(l.pop()) 
     else: 
      a.append(l.pop()) 

    print a, b 
    print sum(a), sum(b) 
    print len(a), len(b) 

Следующий шаг я хотел бы попытаться найти пару чисел из противоположных списков с разностью половину разницы сумм (или близко к что) и поменяйте их.

Answer 2

Один хороший способ подумать об этом, если бы у вас было решение DP для этой проблемы, не могли бы вы использовать его для ответа на сумму подмножества в P разное время? Если это так, ваше решение DP, вероятно, неверно.

Answer 3

Эта проблема выглядит почти как «сбалансированный раздел».

Вы можете использовать подход DP для построения алгоритма псевдополиномиального времени, который решает сбалансированный раздел. См. Проблему 7 в http://people.csail.mit.edu/bdean/6.046/dp/

Похоже, что у вас может быть аналогичный подход.

Answer 4

Это, кажется, экземпляр Partition problem, который является NP-Complete.

Согласно статье Википедии, существует псевдополиномиальное решение динамического программирования времени.

Answer 5

Недавно я решил эту проблему использовать Dynamic Programming в C++. Я не изменил код, чтобы ответить на ваш вопрос. Но нужно изменить некоторые константы и небольшой код.

Приведенный ниже код читает и решает проблемы N. Каждая проблема имеет некоторые люди (в вашем случае число целых чисел) и их веса (целые значения). Этот код пытается разбить набор на две группы с минимальной разницей.

#include <iostream> 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define MAX_PEOPLE 100 
#define MAX_WEIGHT 450 
#define MAX_WEIGHT_SUM MAX_PEOPLE*MAX_WEIGHT 
using namespace std; 

int weights[MAX_PEOPLE]; 
//bool table[MAX_PEOPLE + 1][MAX_WEIGHT_SUM + 1]; 

bool** create2D(int x, int y) { 
    bool **array = new bool*[x]; 
    for (int i = 0; i < x; ++i) { 
     array[i] = new bool[y]; 
     memset(array[i], 0, sizeof(bool)*y); 
    } 
    return array; 
} 

void delete2D(int x, int y, bool **array) { 
    for (int i = 0; i < x; ++i) { 
     delete[] array[i]; 
    } 
    delete[] array; 
} 

void memset2D(int x, int y, bool **array) { 
    for(int i = 0; i < x; ++i) 
     memset(array[i], 0, sizeof(bool)*y); 
} 

int main(void) { 
    int n, N, W, maxDiff, teamWeight, temp; 
    int minWeight = MAX_WEIGHT, maxWeight = -1; 
    cin >> N; 
    while(N--) { 
     cin >> n; 
     W = 0; 
     for(int i = 0; i < n; ++i) { 
      cin >> weights[i]; 
      if(weights[i] < minWeight) 
       minWeight = weights[i]; 
      if(weights[i] > maxWeight) 
       maxWeight = weights[i]; 

      W += weights[i]; 
     } 
     int maxW = maxWeight + (W>>1); 
     int maxn = n>>1; 
     int index = 0; 
    /* 
     table[j][i] = 1 if a team of j people can form i weight 
         from K people, where k is implicit in loop 
     table[j][i] = table[j-1][i-weight[j]] if i-weight[j] >=0 
    */ 
     bool **table = create2D(maxn+1, maxW+1); 
     //memset2D(maxn+1, maxW+1, table); 
     //memset(table, 0, sizeof(table)); 
     table[0][0] = true; 
     /* for k people what can be formed?*/ 
     for(int k = 0; k < n; ++k) { 
      /* forming team of size j out of k people*/ 
      for(int j = min(k, maxn) ; j >= 1; --j) { 
       /* using j people out of k, can I make weight i?*/ 
       for(int i = maxW; i >=minWeight ; --i) { 
        if (table[j][i] == false) { 
         /*do not consider k if more than allowable*/ 
         index = i - weights[k]; 
         if (index < 0) break; 
         /*if without adding k, we can make the weight 
          limit with less than one person then one can 
          also make weight limit by adding k.*/ 
         table[j][i] = table[j-1][index]; 
        } /*outer if ends here*/ 
       } /* ith loop */ 
      } /* jth loop */ 
     } /* kth loop */ 

     maxDiff = MAX_WEIGHT_SUM ; 
     teamWeight = 0; 
     for(int i = 0; i <= maxW; ++i) { 
      if (table[n/2][i]) { 
       temp = abs(abs(W - i) - i); 
       if (temp < maxDiff) { 
        maxDiff = temp; 
        teamWeight = i; 
       } 
      } 
     } 
     delete2D(n+1, maxW+1, table); 
     teamWeight = min(teamWeight, W-teamWeight); 
      cout << teamWeight << " " << W - teamWeight << endl; 
     if(N) 
      cout << endl; 
    } 
     return 0; 
} 

Answer 6

Я написал эту программу в C++ при условии, что максимальная сумма может быть 10000.

#include <iostream> 
#include <vector> 
#include <memory> 
#include <cmath> 

using namespace std; 
typedef vector<int> VecInt; 
typedef vector<int>::size_type VecSize; 
typedef vector<int>::iterator VecIter; 

class BalancedPartition { 
public: 
    bool doBalancePartition(const vector<int>*const & inList, int sum) { 
     int localSum = 0, j; 
     bool ret = false; 
     int diff = INT_MAX, ans=0; 

     for(VecSize i=0; i<inList->size(); ++i) { 
      cout<<(*inList)[i]<<"\t"; 
     } 
     cout<<endl; 
     for(VecSize i=0; i<inList->size(); ++i) { 
      localSum += (*inList)[i]; 
     } 
     M.reset(new vector<int>(localSum+1, 0)); 
     (*M)[0] = 1; 
     cout<<"local sum "<<localSum<<" size of M "<<M->size()<<endl; 

     for(VecSize k=0; k<inList->size(); ++k) { 
      for(j=localSum; j>=(*inList)[k]; --j) { 
       (*M)[j] = (*M)[j]|(*M)[j-(*inList)[k]]; 
       if((*M)[j]) { 
        if(diff > abs(localSum/2 -j)) { 
         diff = abs(localSum/2 -j); 
         ans = j; 
        } 
       } 
      } 
     } 
     mMinDiffSubSumPossible = abs(localSum - 2*ans); 
     return ret; 
    } 

    friend ostream& operator<<(ostream& out, const BalancedPartition& bp) { 
     out<<"Min diff "<<bp.mMinDiffSubSumPossible; 
     return out; 
    } 
    BalancedPartition(): mIsSumPossible(false), mMinDiffSubSumPossible(INT_MAX) { 

    } 
private: 
    shared_ptr<vector<int> > M; 
    bool mIsSumPossible; 
    int mMinDiffSubSumPossible; 
    static const int INT_MAX = 10000; 
}; 

int main(void) { 
    shared_ptr<BalancedPartition> bp(new BalancedPartition()); 
    int arr[] = {4, 12, 13, 24, 35, 45}; 
    vector<int> inList(arr, arr + sizeof(arr)/sizeof(arr[0])); 
    bp->doBalancePartition(&inList, 0); 
    cout<<*bp; 
    return 0; 
}