6

私はこの問題のための合理的なアルゴリズムを考え出そうとしています：

あなたがたくさんのボールを持っているとしましょう。各ボールには少なくとも1つの色がありますが、多色にすることもできます。各ボールにも番号が付いています。それぞれが1色だけの箱もたくさんあります。目標は、ボックス内のボールの数の合計を最大化することであり、唯一のルールは次のとおりです。

  • ボックスにボールを配置するには、少なくともボックスの色が含まれている必要があります
  • 各ボックスに入れることができるボールは1つだけです。

たとえば、青と緑のボールを青いボックスまたは緑のボックスに入れることはできますが、赤いボックスに入れることはできません。

実行時間の点で大いに役立ついくつかの最適化を考え出しました。たとえば、ポイント値の降順でボールを並べ替えることができます。次に、最大数から最小数に進むにつれて、ボールの色が1つだけで、その色を含む高得点のボールが他にない場合は、そのボックスに入れることができます（したがって、そのボックスとそのボールを残りの組み合わせ）。

このタイプの問題にはある種の動的アルゴリズムがあるのか​​、それとも巡回セールスマン問題に変装しているだけなのか、私はただ興味があります。最大でX色あることを知っていれば役に立ちますか？どんな助けでも大歓迎です。ありがとう！

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

ボール：

  • 赤いボール1個-5ポイント
  • 青いボール1個-3ポイント
  • 緑/赤のボール1個-2ポイント
  • 緑/青のボール1個-4ポイント
  • 赤/青のボール1個-1ポイント

ボックス：

  • 赤1個
  • 青1個
  • 1グリーン

最適なソリューション：

  • 赤いボックス内の赤いボール
  • 青いボックスの青いボール

  • 緑のボックスに緑/青のボール

    合計値：12ポイント（5 + 3 + 4）

4

2 に答える 2

12

これは、重み付き2部グラフの最大重みマッチング問題の特殊なケースです。左の頂点がボールに対応し、右の頂点がボックスに対応し、エッジがボールと重みVのボックスを結合するグラフを作成します。ここで、Vはボールをボックスに配置できる場合はボールの番号、それ以外の場合は0です。 。両側に同じ数の頂点ができるまで、重みがゼロのエッジで反対側に結合されたボックスまたはボールを追加します。探している割り当ては、結果のグラフの最大（合計）重みマッチングのゼロ以外の重みのエッジのセットによって決定されます。

代入アルゴリズムはO（n ^ 3）時間で解くことができます。ここで、nは、ハンガリーのアルゴリズムを使用して、ボールまたはボックスの最大数です。（ところで、ハンガリーのアルゴリズムについては、私がよく知っている理論的な結果であり、元の問題がNP困難であるかどうかというタイトルの質問に答えているため、免責事項を作成する必要があります。わかりません。それが実際に使用するのに最適なアルゴリズムであるかどうか。）

于 2010-10-03T00:27:15.513 に答える
0

貪欲なアルグを試しましたか？ポイント/値で並べ替え、可能であればボックスに配置します。例外がある場合は、IDが欠落しているのでそれらを確認してください。

于 2010-10-03T00:29:04.413 に答える