0

値のセットがあり、各値には可能なグループがあります。値は繰り返すことができますが、グループが異なります。

最小数のグループを取得するための最適なアルゴリズムは何ですか

サンプルセット:(12、グループb)(38、グループa)(12、グループa)

望ましい結果:(38、グループa)(12、グループa)

(1つのグループのみが使用されます)

--編集:上記のサンプルのようなセットから最小数のグループを見つけるためのアルゴリズムが必要です。私が悪いアルゴリズムを持っている場合、それは(12、グループb)(38、グループa)を選択しますこれは私が望むものではなく、1つを使用する代わりに同じ値の2つのグループです

4

1 に答える 1

1

質問を正しく理解していれば、これは集合被覆問題です

リンクで説明されている欲張りアルゴリズムは、グループaで始まり、グループaで終了します。これは、すでにすべてをカバーしているためです。

一般に、最適解の近似値しか得られないことに注意してください。

于 2011-06-06T14:53:48.533 に答える