海岛寻宝问题
2019-07-24 Algorithm5个人去一个海岛寻宝，最后一共找到了100枚金币。他们约定了一个分配方案，如下：五个海盗按照抽签的顺序依次提出方案，某一个人提出方案之后，剩余存活的人投票表决：方案需要获得超过半数人的认可之后才能被通过，否则方案提出者将会被扔进大海喂鲨鱼，某一个方案被通过后游戏就结束。注：每个人的投票都是在追求自己利益的最大化：保证自己不会被喂鲨鱼的前提下，尽量使自己分到更多的金币。
题意解读
我们先来理解一下题目意思，如题说的五个海盗按照抽签顺序依次提出方案，所以这是有顺序的，然后半数以上的人认可才能被通过，否则人就没了，比如剩下两个海盗了，那么前面那个海盗就肯定挂了，因为最后那位海盗肯定会投票给自己，只要前面那人挂了他就可以独吞金币。为了解题我们可以先假设一个顺序出来，然后再分析分析怎么make more money
解题思考
我们先给五个海盗按照顺序编个号分别是A、B、C、D、E，在这个游戏中咱们的每个海盗都要考虑两点make more money与活着（注意，这个词我划重点了），刚才我们说到，当只剩俩人时，即只剩D、E时，D肯定就挂了，所以机智的D肯定不能让自己陷入只剩俩人的尴尬处境中。
考虑到这一点是不是有点思路了，我们应该逆向来推这个问题，从两个人的情况开始模拟；
- 剩余D、E
- D必然被投死，收获金币0
- E收获金币100
- 剩余C、D、E
- C需要两票且C知道D不会让自己陷入两人困境肯定会支持自己，再加上自己的票共2票超过了半数，于是大胆的做出了100、0、0的分配
- D收获金币0
- E收获金币0
- 剩余B、C、D、E
- B需要三票且B知道自己死后D、E都收不到一个金币，于是它可以花1个金币把这俩人收买了让他们投自己，再加上自己的票共3票超过了半数，于是做出了98、0、1、1的分配
- C收获金币0
- D收获金币1
- E收获金币1
- 兄弟全在A、B、C、D、E
- A需要三票且A知道自己死后C收不到一个金币，所以可以花1个金币收买了C，还差一票可以在D、E中选一个花2个金币收买让其给自己投票，再加上自己的票共3票超过了半数，于是可以做出97、0、1、2、0或者97、0、1、0、2的分配
- B收获金币0
- C收获金币1
- D/E收获金币2
所以题目的答案是，在第一个位置的人最有利，最多能够分到最多97个金币🙆♂
