皆さん、
問題に遭遇しました...これは興味深いものでした...それを少し修正しています。
一連の整数 (範囲 0 ～ 500) を指定して、2 つの部分集合をほぼ均等に分割して形成できる和の最小差を見つけます。(整数のカウントが n であるとします。n が偶数の場合、各セットには n/2 要素が必要であり、n が奇数の場合、1 つのセットには (n-1)/2 要素があり、もう 1 つのセットには (n+1)/2 要素があります)
サンプル入力: 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 アプローチを使用して、平衡分割を解く疑似多項式時間アルゴリズムを構築できます。http://people.csail.mit.edu/bdean/6.046/dp/の問題 7 を参照してください。
同様のアプローチができるようです。
私は最近、C++ で動的プログラミングを使用してこの問題を解決しました。あなたの質問に答えるためにコードを変更していません。ただし、いくつかの定数と小さなコードを変更するだけで十分です。
以下のコードは、N 個の問題を読み取って解決します。各問題には、何人かの人 (この場合は整数の数) とその重み (整数値) があります。このコードは、差が最小になるようにセットを 2 つのグループに分割しようとします。
#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;
}
それについて考える良い方法の 1 つは、この問題に対する DP ソリューションがあれば、それを使用してサブセット和を P 時間で答えることができるかということです。もしそうなら、あなたの DP ソリューションはおそらく正しくありません。
これは、NP-Complete であるパーティション問題のインスタンスのようです。
ウィキペディアの記事によると、疑似多項式時間動的計画法のソリューションがあります。
最大合計が 10000 になる可能性があると仮定して、このプログラムを C++ で作成しました。
#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)
次のステップでは、反対のリストから合計の差の半分 (またはそれに近い) の差を持つ数字のペアを見つけて、それらを交換しようとします。