私はn個のアイテムを持っています。各アイテムは、値v_iおよび継続確率p_iを有する。私はアイテムを選んでその価値を得、それに対応する確率でプレイを続けるゲームをするつもりです。私が続行するなら、私は残りのアイテムを手に取って、その値を私の合計に加えて、その継続確率に再び従うことができます。私が運が良ければ、アイテムがなくなるまで遊ぶことができます。私は期待値を最大にするために注文を選びたいと思う。ランダム早期終了ゲームのアイテムの最適な順序
これを解決する効率的なアルゴリズムはありますか？
あなたの所見は正しいです！ v_i /（1 - p_i）でソートし、その順序で項目をリストする必要があります。
これがなぜ機能するかを確認するには、まず2項目のケースを見てみましょう。 2つのアイテム（v1、p1）と（v2、p2）があるとします。ピッキング（v1、p1）の予想報酬がピッキングの予想報酬（v2、p2）よりも良い場合、（v1、p1）≥（v2、p2）となるような順序関係を定義することです。最初。
最初に（v1、p1）を選んだ場合、予想される報酬はv1 + p1 v2であり、（v2、p2）を最初に選んだ場合の予想報酬はv2 + p2 v1です。私たちは、発生する
V1 + V2 P1 ≥ V2 + P2 V1
のために起こることがあるかを決定します。いくつかの代数で、我々はこの問題が発生したことを得る場合にのみ
V1 - P2 V1 ≥ V2 - P1 v2の
V1（1 - P2）≥ V2（1 - P1）
V1 /（1-p1）≥ v2 /（1-p2）
これは先に発見したものです。
ここで、好きな順番で要素を選択するとします。表示される順序に基づいて、v1、v2、...、vnに番号を付けましょう。今度は、あなたがこれらのアイテムを選んで、上記の順序に基づいて降順ではないと想像してください。これは、2つの隣接する用語が順不同でなければならないことを意味する。これが起こるのは初めてです。次に予想される報酬は（...
V1 + P1（V2 + P2（V3 + P3を（あろうV_I + P_I（V_ {I + 1} + P_ {I + 1} X））.. Xは、残りの条項からの値です。）
。そして、あなたの報酬は
V1 +になります。あなたは{I + 1}とv_iをV_アイテムを交換することを想像して一人で他のすべてを残しますp1（v2 + p2（v3 + p3 ...（v_ {i + 1} + p_ {i + 1}（v_i + p_i X））...）
ここで主要用語は等しく、すべての非負であるので、我々は今のためにそれらをignkreコア用語に集中できる
V_I + P_I（V_ {I + 1} + P_ {I +1} X）
と
012我々はP_I V_ようV_ {I + 1} + P_ {iが+ 1}（V_I + P_I X）
V_I + {I + 1} ≤ V_ {I + 1} + P_ {I + 1} V_I、V_IおよびV_は{I + 1}が順序から外れていることを知っている
したがって、我々はスワップを行うと仮定すると、我々はその
V_I + P_I（V_ {I + 1} + P_ {I + 1} X）
= V_I + P_I参照v_ {i + 1} + p_i_p_ {i + 1} X
≤ V_ {I + 1} + P_ {I + 1} V_I + P_I P_ {I + 1} X
= V_ {I + 1} + P_ {iは、+ 1}（V_I + P_I Xは）
これは、我々は順序がより多くのソートにするよう期待値だけ上がることができることを意味するので、V_I /の降順でソートするの貪欲溶液（1 - P_I）確かに、最適なソリューションです！
だから、そうです。 v_i /（1 - p_i）でソートし、その順序で物事を列挙します。
素敵な証拠！私は確認するために多くのランダムな例について経験的にチェックしました。 –
面白い問題！好奇心の中で、どこが出てきたのですか？ – templatetypedef
ソーシャルメディアのようなプラットフォームのアイテムのリストをランク付けします。あなたはv_iとp_iを与えるようなモデル（人のような）の確率と継続モデルの確率（人はアイテムを見て、スクロールし続ける）の両方の確率を開発します。あなたはそれらを使ってランク付けし、そのモデルの下で好きなものを最大にしたいと思っています。 v_i /（1 - p_i）の仕分けのようです。 –
ちょうど（私は思う）正解が投稿されました。私は定期的にアルゴリズムのコースを教えて、これは素晴らしい問題を設定する質問になります。帰属と、これを使って私に慣れていただけますか？ – templatetypedef