随机提前终止游戏中物品的最优订单

Question

我有n件物品。每个项目具有值v_i和延续概率p_i。我要玩一个游戏，在那里我挑选一件物品，获得它的价值，并继续玩相应的概率。如果我继续下去，我可以拿起任何剩余的物品，将它的价值加到我的总和上，并且再次受到它的连续概率的影响。如果我很幸运，我可以玩，直到没有剩下的东西。我想选择一个订单来最大化我的预期价值。

有没有一种有效的算法来解决这个问题？

Answer 1

您的观察结果是正确的！您应该按v_i /（1 - p_i）排序并按照该顺序列出项目。

要明白为什么这会起作用，我们首先看两个案例。假设你有两个项目（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。现在想象你已经选择了这些项目，以便它们不是按照上面给出的顺序降序排列的。这意味着必须有两个相邻的术语不合要求。让我们第一次发生这种情况。那么期望的奖励将是

v1 + p1（v2 + p2（v3 + p3（...（v_i + p_i（v_ {i + 1} + p_ {i + 1} X））.. 。）

其中X是从剩余条款的价值。试想一下，你掉的物品V_ {I + 1}和V-I和独自离开一切。然后你的报酬将是

V1 + 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）

和

V_ {I + 1} + {P_ I + 1}（V_I + P_I X）

我们知道，V-I和V - {i + 1}都失灵，所以

V-I + P_I V_ {I + 1} ≤ V_ {I + 1} + P_ {I + 1} V-I

因此，假设我们执行交换，我们看到，

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）排序并按顺序列出事件。