5

バックトラッキング関数に問題があり、特定のデータでループします。プログラムコード全体をここに書くことはできませんが、関数をここに置くことはできます。

bool shareMoney(int quantity, int *values, int index, int moneyA, int half, bool *ifChosen)
{

    if(moneyA == half)
        return true;
    else if(index >= quantity)
        return false;

    moneyA += values[index];

    if(shareMoney(quantity, values,index+1, moneyA, half, ifChosen))
    {
        ifChosen[index] = true;
        return true;
    };

    moneyA -= values[index];

    if(shareMoney(quantity, values,index+1, moneyA, half, ifChosen))
    {
        ifChosen[index] = false;
        return true;
    };

    return false;
}

ここに説明があります：

quantity - 値配列内の要素
の数 values -数値の配列
index - 再帰を制御する
変数 moneyA - 配列値の要素の合計を格納する変数half -
再帰が行われた後に moneyA が到達する必要がある数値
配列値を参照します

この関数は、長さの値の配列である要素の数量を取得します。値は、数値を含む配列を最高のものから最低のものに並べ替え、インデックスは再帰を制御し、デフォルトは 0 であるため、最初の要素から開始します。money からの数値を格納する変数値配列と、値配列から合計された数値の半分である半分に達する必要があり、ifChosen は選択された数値を格納します。

関数全体がこれを行い、values 配列の要素を合計し、半分未満の場合は半分に達したかどうかをチェックし、それを moneyA に追加し、ifChosen でマークしてから、合計が半分より大きい場合は次の要素に進みます戻り、ifChosen 配列でマークを外し、moneyA から減算します。常に最高の要素を取得する必要があります。

簡単な例を次に示します。

6 - number of elements
50, 20, 19, 15, 2, 2 - elements stored in values array
total sum is - 108
half of elements - 54

この結果は次のようになります。

50, 2, 2 - marked as true in ifChosen
20, 19, 15 - marked as false in ifChosen

もちろん、この単純な例では素晴らしい仕事をしますが、より多くの数字を持ち、1 つの数字が複数回出現するより複雑な例では、ループして再帰が停止しません。私は実際にこれに1.5週間取り組んでおり、すべての友人に尋ねましたが、何が問題なのか誰も知りません. ナップザックの問題と少し関係があることは知っていますが、まだそれを持っていないので、まだ勉強する必要があります.

役立つ回答をお待ちしております。

句読点で申し訳ありませんが、私は初めてここに来て、フォーマットに慣れていませんでした。

ここに1つの例があります： 

89 86 83 67 53 45 5 1    

44 43 34 33 33 24 23 23 23 22 21 21 19 12 11 9 8 7 5 3 2 2 2 1 1 1 1 1     

real    0m28.007s    

user    0m27.926s    

sys 0m0.028s

今、私はそれが永遠にループすると思うもの: 43 要素:

12 2 2 1 3 4 5 6 7 89 33 12 45 23 44 23 11 44 1 3 5 7 88 33 8 19 43 22 86 5 34 23 21 67 83 24 21 53 9 11 34 1 1

@Karl Bielefeldtはい、非常に多くの組み合わせがあることを知っているので、速度を上げようとしています。今のところこれですべてですが、特定の入力に対して間違った結果が得られます。誰でもそれを修正できますか?以前よりもはるかに高速に動作しますか? 

bool shareMoney(int quantity, int *values, int index, int moneyA, int half, bool *ifChosen){

if(index>=quantity && moneyA == half){ return true;}
else if(index>=quantity) return false;

moneyA+=values[index];
ifChosen[index]=true;

if(moneyA<=half){       
    shareMoney(quantity,values,index+1,moneyA, half,ifChosen);
    if(moneyA==half) return true;

    return true;
}else{
    shareMoney(quantity,values,index+1,moneyA, half,ifChosen);      
    moneyA-=values[index];
    ifChosen[index]=false;

    return true;
}


return false;}
4

2 に答える 2

2

このような問題の反復回数を削減する典型的な方法は、線形計画法を解くことによってサブツリーの境界を計算することです (問題と同様ですが、残りの変数は分数値を取ることができます)。シンプレックスは、線形計画法を指数ではなくほぼ 2 次時間で解きます。線形計画法の最適な解は、同じ制約を持つ最適な整数またはバイナリの解と少なくとも同じくらい優れているため、線形解が現在の最良の解よりも悪い場合は、徹底的な評価を行わずにサブツリー全体を破棄できます。

編集:ブルートフォースアルゴリズムを単純化することから始めましょう:

int* shareMoney( int pool_size, int *pool, int *solution, int cumsum, int goal)
{
    if (cumsum == goal) return solution;
#if PRUNE_ABOVE
    if (cumsum > goal) return 0;
#endif
    if (!pool_size) return 0;

#if PRUNE_BELOW
    int max = cumsum;
    for( int n = pool_size; n--; max += pool[n] );
    if (max < goal) return 0;
#endif

    int* subproblem = shareMoney(pool_size-1, pool+1, solution, cumsum, goal);
    if (subproblem) return subproblem;

    *solution = *pool;
    return shareMoney(pool_size-1, pool+1, solution+1, cumsum+*pool, goal);
}

実行後solution、ゴールに到達するために使用された値のリストが含まれ、返されたポインターはリストの最後を示します。

条件付きブロックは、私が最初に提案した改善です。これらの場合、再帰は必要ありません。

各ステップで max を計算するために反復する必要をなくすことができます。

int* shareMoney( int pool_size, int *pool, int *solution, int cumsum, int poolsum, int goal)
{
    if (cumsum == goal) return solution;
#if PRUNE_ABOVE
    if (cumsum > goal) return 0;
#endif
    if (!pool_size) return 0;

#if PRUNE_BELOW
    if (cumsum + poolsum < goal) return 0;
#endif

    int* subproblem = shareMoney(pool_size-1, pool+1, solution, cumsum, poolsum - *pool, goal);
    if (subproblem) return subproblem;

    *solution = *pool;
    return shareMoney(pool_size-1, pool+1, solution+1, cumsum+*pool, poolsum - *pool, goal);
}

整数バージョンを解決する関数は次のとおりです (コインの金種が繰り返される場合に適しています)。

int* shareMoney( int pool_size, int *pool_denom, int *pool_cardinality, int *solution, int cumsum, int poolsum, int goal)
{
    if (cumsum == goal) return solution;
#if PRUNE_ABOVE
    if (cumsum > goal) return 0;
#endif
    if (!pool_size) return 0;

#if PRUNE_BELOW
    if (cumsum + poolsum < goal) return 0;
#endif

    poolsum -= *pool_cardinality * *pool_denom;
    for (*solution = *pool_cardinality; *solution >= 0; --*solution) {
        int* subproblem = shareMoney(pool_size-1, pool_denom+1, pool_cardinality+1, solution+1, cumsum + *solution * *pool_denom, poolsum, goal);
        if (subproblem) return subproblem;
    }

    return 0;
}

個々のコインの単純なリストを取得する代わりに、金種のリストと各コインの利用可能なコインの数を取得します。結果は、ソリューションに必要な各金種のコインの数です。

于 2011-02-23T22:01:59.283 に答える
0

43 要素の場合、9 兆近くの可能な組み合わせがあります。9 兆すべてをチェックする必要がある場合、それを高速化する方法はありませんが、それほど長く待ちたくない場合は、答えをループの開始点の近くに置くようにしてください。昇順で並べ替えることで、おそらく正しい解決策を見つけたと思います。これは、最初に大きな断片を配置するため、おそらく高速です (深さ優先の再帰を行っているため)。

問題を正しく理解していれば、合計値のちょうど半分になる最小の要素の組み合わせが見つかります。つまり、選択されていない要素も合計値のちょうど半分になる必要があり、最大の要素になります。

于 2011-02-23T21:07:49.743 に答える