海盗分金

· · 个人记录

海盗分金

1.1 经典模型

有 n 个人，m 个金币，首先由 1 号来提出分配方案，然后 n 个人进行表决，如果超过一半人同意，则通过，否则当前提出方案的人会被杀。问 1 号在保证自己存活的情况下，最多获得多少颗金币？（假设每个人都聪明绝顶，且乐于其他人死）

1.2 推理过程

采用逆推法。

不妨以 n = 5, m = 100 来举例。

如果 1 至 3 号强盗都死了，只剩 4 号和 5 号的话，5 号一定投反对票让 4 号死，以独吞全部金币。

所以，4 号惟有支持 3 号才能保命。

不过，$2$ 号推知 $3$ 号的方案，就会提出 $(98,0,1,1)$ 的方案，即放弃 $3$ 号，而给予 $4$ 号和 $5$ 号各一枚金币。 由于该方案对于 $4$ 号和 $5$ 号来说比在 $3$ 号分配时更为有利，他们将支持他而不希望他出局而由 $3$ 号来分配。这样，$2$ 号将拿走 $98$ 枚金币。 同样，$2$ 号的方案也会被1号所洞悉，$1$ 号并将提出 $(97,0,1,2,0)$ 或 $(97,0,1,0,2)$ 的方案，即放弃 $2$ 号，而给 $3$ 号一枚金币，同时给 $4$ 号（或$5$ 号）$2$ 枚金币。 由于 $1$ 号的这一方案对于 $3$ 号和 $4$ 号（或 $5$ 号）来说，相比 $2$ 号分配时更优，他们将投 $1$ 号的赞成票，再加上 $1$ 号自己的票，$1$ 号的方案可获通过，$97$ 枚金币可轻松落入囊中。 ### $1.3$ 代码实现 可以用**动态规划**解决。 设 $f_{i,j}$ 表示有 $i$ 个人，$j$ 个金币时 $i$ 号能拿到的最多钱数（我们这里相当于逆推了，现实意义应该是 $1$ 号所能拿到的最多钱数） 令 $x = \lfloor\dfrac{i}{2} \rfloor$ 表示需要额外贿赂的人数，$w$ 表示贿赂出去的钱 考虑转移： 第 $i$ 个人肯定会去尽量选择贿赂那些第 $i - 1$ 个少贿赂的人 * $f_{i - 1, j} = 0$，第 $i - 1$ 个人无法拿到任何金币，即用 $j$ 个金币去贿赂了 $\lfloor\dfrac{i - 1}{2}\rfloor$ 个人，剩下的 $\lceil\dfrac{i -1}{2}\rceil$ 个人（包括 $i - 1$）一定是没有分到钱的。 那么对于第 $i$ 个人，他会选择贿赂 $\lceil \dfrac{i - 1}{2} \rceil = \lfloor \dfrac{i}{2} \rfloor$ 个人，最后再算上自己。 他需要贿赂的钱 $w = x$，即 $j - x \to f_{i,j}

需要注意的是，i < 5 的情况需要提前算出（已在上述的推理过程中给出）。

时间复杂度 \mathcal{O}(nm)

2.1 模型拓展

上一模型是在支持人数严格大于一半的情况下，但很多时候，支持人数等于一半即算通过，我们来考虑这样的情况。

还是考虑 n = 5,m = 100 的情况：

$4$ 号：如果 $3$ 号提的方案一定能获得通过（原因：$3$ 号给 $5$ 号的金币大于$0$， $5$ 号就同意。因此就能通过），那自己获得的金币就为 $0$，所以只要 $2$ 号让自己获得的金币大于 $0$ 就会同意。 $3$ 号：因为到了自己提方案的时候可以给 $5$ 号一金币，自己的方案就能通过，但考虑到 $2$ 号提方案的时候给 $4$ 号一个金币，$2$ 号的方案就会通过，那自己获得的金币就为 $0$。所以只要 $1$ 号让自己获得的金币大于 $0$ 就会同意。 $2$ 号：因为到了自己提方案的时候只要给 $4$ 号一金币，就能获得通过，根本就不用顾及 $3$ 号 $5$ 号同意不同意，所以不管 $1$ 号怎么提都不会同意。 $1$ 号：$2$ 号肯定不会同意。但只要给 $3$ 号一块金币，$5$ 号一块金币就能获得通过。 所以答案是 $(98,0,1,0,1)

2.2 归纳总结

假设有 n 个人，m 个金币