これは動的でも貪欲でもありません。最初に別の問題を見てみましょう。すべての人を最大 1 回選択するだけで解決できますか?
あなたは P 人と S セットを持っています。セットと人を表す S+P 頂点を持つグラフを作成します。人物 pi と集合 si の間にはエッジがあり、pi は si の要素です。これは二部グラフであり、問題の決定バージョンは、そのグラフで一致する最大カーディナリティのサイズが S であるかどうかをテストすることと同じです。
そのページで詳しく説明されているように、この問題は最大フローアルゴリズムを使用することで解決できます (注: 何について話しているのかわからない場合は、時間をかけて読んでください。残りの部分は理解できません)。それ以外の場合): 最初にスーパーソースを作成し、それを容量 1 のすべての人にリンクするエッジを追加します (各人が 1 回しか使用できないことを表します)。次に、スーパーシンクを作成し、すべてのセットを容量のあるシンクにリンクするエッジを追加します。 1 (各セットが 1 回しか使用できないことを表す) を指定し、ソースとシンクの間で適切な最大フロー アルゴリズムを実行します。
ここで、少し異なる問題を考えてみましょう: すべての人を最大k回選択することで解決できるでしょうか?
最後の段落の注意事項に注意を払った場合は、答えがわかるはずです。この場合、各人が複数回使用される可能性があることを示すために、スーパー ソースを離れるエッジの容量を変更するだけです。
したがって、これで、人が最大k回選択される決定問題を解くアルゴリズムが得られました。k で実行できる場合は、k より大きい任意の値でも実行できること、つまり単調関数であることは簡単にわかります。したがって、問題の決定バージョンで二分探索を実行して、まだ機能する最小の k を探すことができます。
注: k の各値を順番にテストし、ゼロから始めるのではなく、最後の実行で得られた残差ネットワークを拡張することで、二分探索を取り除くこともできます。ただし、二分探索版の方が概念的に簡単なので説明することにしました。