0

私は比較的複雑な問題を抱えています。合計が X になる配列から可能なすべてのサブ配列を見つけるアルゴリズムが必要なので、指定された配列の場合:

{2,8,12,45,32,7,6,5}

合計が 20 になる部分配列が必要だとしましょう。一部は次のようになります。

{8,12} {2,7,6,5} {12,6,2}

ただし、次のような組み合わせがあります。

{7,7,6} {5,5,5,5} {8,8,2,2}

可能なすべての金額が必要になります。

私はすべての可能性のブルート フォース チェックを行うソリューションを実行しましたが、完了するまでに時間がかかりすぎる (場合によっては 30 分以上) ため、2、3 頭頭を悩ませてきたよりスマートなソリューションが必要です。数日。

4

1 に答える 1

1

あなたの質問は、繰り返し数が受け入れられる回答を示しているようであり、加数を順序付けることができるすべての可能な方法を生成したくない. それを踏まえて回答します。

これを C++ で実装します。データ構造として、おそらく次のようなものを使用します。

struct partial_sum {
  int min_last_summand;
  std::vector< std::pair<partial_sum*, int> > prefixes;
};

std::map<int, partial_sum*> m;

ここで中心的な部分はマップmです。合計の値を、それを取得する方法に関する情報にマップします。0にマップして初期化しNULLます。メンバーは、特定の合計を取得するために考えられるすべてのprefixes方法に関するデータを格納します。各ペアの最初の部分は、最後の部分を除くすべての被加数に関する情報へのポインターを提供し、2 番目の部分は最後のメンバーを提供します。これにより、有向非巡回グラフの形式が得られます。合計は多くの合計の接頭辞になる可能性があり、合計はさまざまな接頭辞を持つことができますが、すべての接頭辞の合計の値は現在の合計の値よりも小さくなります。

中央の反復ステップでは、 から最小限のエルケメントを削除しm、入力セットから削除したばかりの値に要素を追加できるすべての可能な方法を生成します。したがって、新しい合計に新しいエントリを挿入する必要があるかどうかをマップで確認します。prefixesまた、既存のエントリと新しいエントリの両方について、マップから削除したポインタを最初の部分として、最後に追加した加数を 2 番目の部分として、リストに新しい項目を作成します。

すべての順列の生成を避けるために、加数の昇順 (またはむしろ非降順) で合計を生成するだけです。物事を簡単にするために、このmin_last_summand情報を維持します。リスト内のペアのすべての 2 番目の要素の最小値が常に含まれている必要がありprefixesます。新しい合計を生成するとき、最後の被加数が接頭辞の最小の最後の被加数よりも小さい場合はスキップできます。また、合計値が目標の合計よりも大きい合計を生成しないようにすることもできます。

結果を印刷するときは、ターゲット合計から到達可能な DAG の部分を再帰し、そこから root までのすべてのパスをリストする必要がありますNULL。したがって、各再帰ステップで、現在の部分合計へのポインターが得られます。そのポインターがNULLの場合、被加数がゼロの合計を出力します。それ以外の場合は、すべてを反復処理しますprefixes。各プレフィックスについて、そのプレフィックスを記述するすべての可能な方法を生成するために再帰しますがmin_last_summand、最初の要素の が現在の最後の加数より大きくない場合、および 2 番目の要素がそれに続く加数より大きくない場合のみです。 . つまり、次の被加数を引数として再帰呼び出しに渡す必要があります。まとめると、これにより、降順のステップを含む合計の生成が回避されます。

上記のアプローチは、プログラムが 1 回の実行後に終了することを前提としているため、メモリの解放について心配する必要はありません。その場合、おそらく作成したすべてのオブジェクトへのポインタを保存する必要があるため、それらをすべて解放できます。

于 2012-10-19T07:04:05.370 に答える