4

Backtracking大学でアルゴリズムを学び始めたばかりです。どういうわけか、部分和問題のプログラムを作成することができました。正常に動作しますが、プログラムがすべての可能な組み合わせを提供していないことがわかりました。

例：目標の合計には100の組み合わせがあるかもしれませんが、私のプログラムは30しか与えません.コードは次のとおりです。誰かが私の間違いを指摘してくれると助かります。

int tot=0;//tot is the total sum of all the numbers in the set.
int prob[500], d, s[100], top = -1, n; // n = number of elements in the set. prob[i] is the array with the set.
void subset()
{
    int i=0,sum=0; //sum - being updated at every iteration and check if it matches 'd'
    while(i<n)
    {
        if((sum+prob[i] <= d)&&(prob[i] <= d)) 
        {
            s[++top] = i;
            sum+=prob[i];
        }
        if(sum == d) // d is the target sum 
        {
            show(); // this function just displays the integer array 's'
            top = -1; // top points to the recent number added to the int array 's'
            i = s[top+1];
            sum = 0;
        }
        i++;
        while(i == n && top!=-1)
        {
            sum-=prob[s[top]];
            i = s[top--]+1;
        }
    }
}

int main()
{
    cout<<"Enter number of elements : ";cin>>n;
    cout<<"Enter required sum : ";cin>>d;
    cout<<"Enter SET :\n";
    for(int i=0;i<n;i++)
    {
        cin>>prob[i];
        tot+=prob[i];
    }
    if(d <= tot)
    {
        subset();
    }
    return 0;
}

プログラムを実行すると：

Enter number of elements : 7
Enter the required sum : 12
Enter SET : 
4 3 2 6 8 12 21

SOLUTION 1 : 4, 2, 6
SOLUTION 2 : 12

4、8も解決策ですが、私のプログラムでは表示されません。入力数が 100 以上の場合はさらに悪化します。少なくとも 10000 の組み合わせがありますが、私のプログラムは 100 を示しています。

私が従おうとしているロジック：

  1. サブセットの合計がターゲットの合計以下である限り、メイン SET の要素をサブセットに取り込みます。
  2. サブセットの合計に特定の数を追加すると、それがターゲットよりも大きくなる場合、それは取りません。
  3. セットの最後に到達し、答えが見つからない場合、セットから最後に取得された番号を削除し、削除された最近の番号の位置の後の位置にある番号を調べ始めます。（配列「s」に保存するのは、メインSETから選択した番号の位置であるため）。
4

3 に答える 3

1

スタックフリーの解決策が可能かもしれませんが、バックトラッキング アルゴリズムを実装する通常の (そして一般的に最も簡単な!) 方法は、再帰を使用することです。

int i = 0, n;    // i needs to be visible to show()
int s[100];

// Considering only the subset of prob[] values whose indexes are >= start,
// print all subsets that sum to total.
void new_subsets(int start, int total) {
    if (total == 0) show();    // total == 0 means we already have a solution

    // Look for the next number that could fit
    while (start < n && prob[start] > total) {
        ++start;
    }

    if (start < n) {
        // We found a number, prob[start], that can be added without overflow.
        // Try including it by solving the subproblem that results.
        s[i++] = start;
        new_subsets(start + 1, total - prob[start]);
        i--;

        // Now try excluding it by solving the subproblem that results.
        new_subsets(start + 1, total);
    }
}

次に、これをmain()with で呼び出しますnew_subsets(0, d);。再帰は最初は理解するのが難しいかもしれませんが、理解することが重要です。上記が意味をなさない場合は、より簡単な問題 (フィボナッチ数を再帰的に生成するなど) を試してください。

代わりにあなたが与えた解決策を使って作業すると、私が見ることができる1つの問題は、解決策を見つけるとすぐにそれを一掃し、これに含まれていた最初の番号の右側にある番号から新しい解決策を探し始めることです.解決策 (をtop = -1; i = s[top+1];意味i = s[0]し、それに続く がありますi++;)。これにより、同じ最初の番号で始まるソリューションが失われます。if (sum == d) { show(); }それらすべてを確実に取得するには、代わりに行う必要があります。

最初は内部whileループがかなり混乱していることに気づきましたが、実際には正しいことをしていると思います.i配列の最後に達すると、部分的なソリューションに追加された最後の番号が削除され、この番号が配列の最後の番号であった場合、再びループして、最後から 2 番目の数値を部分解から削除します。部分解に含まれる数値はすべて異なる位置にあるため、2 回以上ループすることはありません。

于 2013-03-31T14:38:02.000 に答える
1

見つけようとしている解決策は、ステップ 1 の「as long as」句により、セット内のエントリの順序によって異なります。

目標を超えない限りエントリを取得する場合、たとえば「4」と「2」を取得すると、「2」が含まれている限り、「8」が目標を取得します。 '8' より前のセットでは、'4' と '8' でサブセットを取得することはありません。

エントリの追加をスキップする可能性を追加する (または、あるサブセットに追加し、別のサブセットには追加しない) か、セットの順序を変更して再調査する必要があります。

于 2013-03-31T12:47:10.067 に答える