12

伙计们,

遇到了一个问题...发现这很有趣...正在对其进行一些修改,只是加油。

给定一组整数(范围 0-500),找出两个子集之和之间的最小差异,该差异可以通过将它们几乎均分来形成。(比如说整数的个数是 n,如果 n 是偶数,每个集合必须有 n/2 个元素,如果 n 是奇数,一个集合有 (n-1)/2 个元素,另一个有 (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 方法。

多谢你们...

拉杰...

4

6 回答 6

9

这个问题看起来几乎像“平衡分区”。

您可以使用 DP 方法构建求解平衡分区的伪多项式时间算法。请参阅http://people.csail.mit.edu/bdean/6.046/dp/上的问题 7

听起来您可以采用类似的方法。

于 2010-11-18T13:30:49.103 回答
2

我最近使用 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;
}
于 2010-11-21T09:48:09.683 回答
1

考虑它的一个好方法是,如果你有这个问题的 DP 解决方案,你能用它在 P 时间内回答子集总和吗?如果是这样,那么您的 DP 解决方案可能不正确。

于 2010-11-18T06:17:16.497 回答
0

我用 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;
}
于 2014-01-16T09:28:15.023 回答
0

这似乎是分区问题的一个实例,它是 NP-Complete。

根据维基百科的文章,有一个伪多项式时间动态规划解决方案。

于 2010-11-18T14:05:21.597 回答
-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)

下一步,我将尝试从相反的列表中找到一对数字,其差为总和差的一半(或接近),然后交换它们。

于 2010-11-18T06:11:03.207 回答