10

私はこれがここでたくさん話されたことを知っています、しかし私はこの問題に苦労しています。

[3、1、1、2、2、1]などの一連の数値があり、それを2つのサブセットに分割する必要があるため、各合計は等しいか、差が最小になります。

ウィキペディアのエントリ、このページ（問題7）、ブログのエントリを見てきました。

しかし、リストされているすべてのアルゴリズムはYES / NOの結果しか得られず、それらを使用して2つのサブセットを出力する方法を本当に理解していません（たとえば、S1 = {5、4}およびS2 = {5、3、3}）。ここで何が欠けていますか？

4

4 に答える 4

4

疑似多項式アルゴリズムは、最適化問題ではなく、決定問題に対する答えを提供するように設計されています。ただし、例のブール値の表の最後の行は、現在のセットが N/2 まで合計できることを示していることに注意してください。

最後の行で、ブール値が である最初の列を取得しますtrue。次に、指定された列のセットの実際の値を確認できます。セットの合計値が N/2 の場合、パーティションの最初のセットが見つかりました。それ以外の場合は、どのセットが N/2 の差になる可能性があるかを確認する必要があります。上記と同じアプローチを使用できますが、今回は差dです。

于 2012-10-08T12:05:13.860 に答える
1

これはO(2^N)になります。ここでは動的計画法は使用しません。関数の実行後に、result1、result2、および差分を出力できます。これが役立つことを願っています。

vector<int> p1,p2;
vector<int> result1,result2;
vector<int> array={12,323,432,4,55,223,45,67,332,78,334,23,5,98,34,67,4,3,86,99,78,1};

void partition(unsigned int i,long &diffsofar, long sum1,long sum2)
{
    if(i==array.size())
    {
        long diff= abs(sum1 - sum2);
        if(diffsofar > diff)
        {
            result1 =  p1;
            result2 = p2;
            diffsofar = diff;
        }
        return;
    }

    p1.push_back(array[i]);
    partition(i+1,diffsofar,sum1+array[i],sum2);
    p1.pop_back();

    p2.push_back(array[i]);
    partition(i+1,diffsofar,sum1,sum2+array[i]);
    p2.pop_back();

    return;
}
于 2014-11-29T18:13:59.013 に答える
0

私は最近この同じ問題に直面し、それについての質問を投稿しました (ここ: Variant of Knapsack )。私の場合の違いは、結果のサブセットが同じサイズでなければならないことです (元のセットに偶数の要素がある場合)。それを保証するために、@Sandesh Kobalの回答に数行追加しました。

void partition(unsigned int i,long &diffsofar, long sum1,long sum2)
{
    int maxsize = (array.size()+1)/2;

    if(p1.size()>maxsize)
        return;

    if(p2.size()>maxsize)
        return;

    if(i==array.size())
    {
        ...

また、 を両方とも呼び出した後partition、 を追加しましif(diffsofar==0) return;た。最適解がすでに見つかっている場合は、検索を続ける意味はありません...

于 2016-01-30T01:02:30.207 に答える