最も収益性の高い手配を見つける最大の流れ

Question

Let a_1, ..., a_n俳優。各俳優の費用はc_1, ..., c_nです。また、我々は投資家がb_1,..., b_mを持っているので、各投資家はq_jを私たちの映画のお金に使っています。投資家が彼の好きな俳優のすべてが私達の映画の中にあれば、投資家は私たちの映画にお金を入れるでしょう。 もちろん、複数の投資家がいるかもしれません。私たちの利益（投資マイナス給与の合計の、すなわち合計）

は、基本的には解決策が重量q_iの縁と各投資家にいくつかの頂点sを接続することですを最大化するために俳優/投資家のサブセットを検索します。次に、各投資家を重みの端のある俳優に接続します。infinity最後に、各アクターを、ある程度の頂点tに接続し、エッジの重みはc_iです。

次に、最大フローを探します。

私の質問は以下のとおりです。

• なぜそれが動作しますか？
• 私は、これらの俳優/投資家のサブセットを見つけるには、最小限のカット(S,T)を見る必要があり、次に、picked_investors = S ∩ investorsとpicked_actors = S ∩ actorsがあると言われました。あなたはそれを説明できますか？
• フローが2つのサブセットを見つけるためにどこを見てもらえませんか？

Answer 1

このアルゴリズムは、最大フロー - 最小カット二重性に基づいています。このグラフのミニカットがどのように見えるかを分析してみましょう。

有限の解が可能であることが容易にわかります。片側に{s}、反対側に他のノードを持つカットを考えてみましょう。明らかに、このカットの値は、有限であるq_iの合計です。

ここで、このグラフのカットの意味を見てみましょう。投資家がカット内のsと同じ側にいる場合、彼/彼女は彼/彼女のお金を投資することを意味します。俳優がカットの中でsと同じ側にいる場合、彼はまた映画に参加することを意味します。カットの反対側にいるということは、映画に参加していないことを意味する（俳優と投資家の両方にとって）。

重要な部分は次のとおりです。ステートメントに記載されている制限を満たさないカットは、投資家からカットを横切る俳優までのエッジが存在するため、無限の価値を持ちます。これまで見てきたように、有限の解が存在するので、mincutは制限を満たすでしょう。

今、私たちは何を最小限に抑えていますか？無限端を無視して、ムービーのアクターを選択すると、ムービーの投資家を選んでいない場合、投資家のエッジが追加された場合、アクターのエッジが値に追加されます。利益を最大化したいと思っています。それは、失うものを最小限に抑えることと同じです。