Люди,
наткнулся на проблему... нашел это интересное... немного изменил его, просто переработав его.
Учитывая набор целых чисел (диапазон 0-500), найдите минимальную разницу между суммой двух подмножеств, которые могут быть сформированы путем их разбиения почти одинаково. (скажем, число целых чисел равно n, если n четно, каждое множество должно иметь n/2 элементов, а если n нечетно, то в одном наборе есть (n-1)/2 элементов, а у другого есть (n + 1)/2 элемента)
sample 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 для этой проблемы.
Спасибо, ребята...
Радж...
Эта проблема выглядит почти как "сбалансированный раздел".
Вы можете использовать подход DP для построения алгоритма псевдополиномиального времени, который решает сбалансированный раздел. См. Проблему 7 в http://people.csail.mit.edu/bdean/6.046/dp/
Похоже, у вас может быть аналогичный подход.
Я решил эту проблему недавно использовать Dynamic Programming в С++. Я не изменил код, чтобы ответить на ваш вопрос. Но изменение некоторых констант и небольшого кода должно выполняться.
Нижеприведенный код читает и решает проблемы 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;
}
Один хороший способ подумать об этом будет, если бы у вас было решение DP для этой проблемы, можете ли вы использовать его для ответа на сумму подмножества в течение P-времени? Если это так, ваше решение DP, вероятно, неверно.
Это, кажется, экземпляр проблема раздела, которая NP-Complete.
Согласно статье Википедии, существует псевдополиномиальное решение динамического программирования времени.
Я написал эту программу на С++, предполагая, что максимальная сумма может быть 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;
}
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)
В следующем шаге я попытался бы найти пару чисел из противоположных списков с разностью половин разницы сумм (или близко к ним) и поменять их.