7

私には4つのグループがあるとしましょう

A [0、4、9]

B [2、6、11]

C [3、8、13]

D [7、12]

ここで、各グループ（つまり新しいグループ）E [Aの数、Bの数、Cの数、Dの数]から1つの数が必要です。これにより、Eの最大数とEの最小数の差は次のようになります。これはどのような種類の問題ですか？この種の問題を解決するには、どのグラフアルゴリズムが適していますか？前もって感謝します。

PS：私はこれをJavaで解決しようとしていますが、タイトルが指定されていないことをお詫びします。

編集：最後に、実際に探しているものを見つけましたhttp://rcrezende.blogspot.in/2010/08/smallest-relevant-text-snippet-for.html

4

2 に答える 2

4
  1. すべてのグループの内容を1つの配列に結合します。配列の各要素は、（数値、グループ名）のペアである必要があります。
  2. この配列を番号で並べ替えます。
  3. 2つのイテレータを次々に進めます。すべてのグループの要素がこれらのイテレータの間にあるとは限らない場合は、最初のイテレータを移動します。これらのイテレータの間に各グループの要素がある場合は、2番目のイテレータを移動します。詳細については、この質問を参照してください。
  4. イテレータ間の最小距離によって、最適な結果のグループが決まります（同じグループの代表者が複数いる場合にのみ、不要な要素を削除する必要があります）。

その他のアルゴリズム：

  1. 各グループの要素を並べ替えます（まだ並べ替えられていない場合）。
  2. 各グループの最小要素のペア（番号、グループ名）を優先度キュー（最小ヒープ、優先度=番号）に入れます。
  3. キューから最小の要素を削除し、同じグループの次の要素に置き換えます。
  4. 一部のグループに要素がなくなるまで、手順3を繰り返します。各反復のmax（queue）-min（queue）を計算し、それが以前の値よりも小さい場合は、これまでの結果の最良のグループを更新します。
于 2012-08-25T17:34:20.337 に答える
2

迅速に終了することで、徹底的な検索を行うことができると思います。見た目ほど悪くはありません。

たとえば、AとBから番号を選択する場合、Cからこれらの2つの番号に最も近い2つの番号を選択できますが、他の番号を使用しても、より良い結果は得られません。

  • Aの各要素について：それを呼び出しますa、あなたは区間（a、a）に近い数を探しています
  • 次に、各グループについて、最も近い番号を選択します（バイナリ検索で実行できます）。これで、（a、b1）または（b2、a）のいずれかの新しい検索間隔ができました。

例：

  • Aから4を選び、（4,4）の近くを検索します
  • A）Bから2を選び、（2,4）の近くを検索します
  • .... Cから3つ選んでください、それは間隔内にあります。（2,4）の近くを検索
  • .... Dから7を選択し、間隔は（2,7）、距離は5です。
  • B）Bから6を選び、（4,6）の近くを検索します
  • ...。
于 2012-08-25T17:37:58.073 に答える