海盗分金算法实现

2023-03-05 11:37:02Python09

海盗分金算法实现,第1张

海盗分金 分配原则：等级最高的海盗提出一种分配方案。所有的海盗投票决定是否接受分配,包括提议人。并且在票数相同的情况下,提议人有决定权如果提议通过,那么海盗们按照提议分配金币。如果没有通过,那么提议人将被扔出船外,然后由下一个最高职位的海盗提出新的分配方案。 wiki

假设每一个海盗都很机智,先利己再损人,按优先级遵守如下3条原则：

1. 自己要能活下来。

2. 拿更多的银子.哦!不,是金子!

3. 好想看排在前面的海盗被丢到海里。

算法实现思路 :首先根据策略算出除自己外还需要多少票,接着算出可以用金币收买多少海盗,然后算出为了保命而投票的海盗数,如果两者相加都不够,只能被丢到海里。问题的难点在于随着人数的增多,为了保命而投票的海盗数会动态变化。大家可以思考一下,如果有50个海盗分配5个金币,按照规则,有哪些海盗必死无疑，而哪些海盗能够幸运地活下来。

以下是java算法实现:

个人意见是：先倒过来考虑，最少是剩下4和5两个人，4提出（100：0），5肯定不同意，而4自己同意（2个人，有一个人同意，正好二分之一），所以方案通过。4号强盗最多100个金币。

所以5会支持3，那么3，4和5三个人，3提出（99：0：1），3和5会同意，方案通过。3号强盗最多99个金币。

如果是2，3，4和5，2会提出（98：0：0：2），2和5会同意，方案通过。2号强盗最多98个金币。

如果是1，2，3，4和5，1会提出（98：0：1：1:0),1,3he 5三个人会同意，方案通过。1号强盗最多98个金币。

网上答案是：从后向前推，如果1至3号强盗都喂了鲨鱼，只剩4号和5号的话，5号一定投反对票让4号喂鲨鱼，以独吞全部金币。所以，4号惟有支持3号才能保命。

3号知道这一点，就会提出“100，0，0”的分配方案，对4号、5号一毛不拔而将全部金币归为已有，因为他知道4号一无所获但还是会投赞成票，再加上自己一票，他的方案即可通过。

不过，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号能够获取最大收益的方案了！答案是：1号强盗分给3号1枚金币，分给4号或5号强盗2枚，自己独得97枚。分配方案可写成（97，0，1，2，0）或（97，0，1，0，2）。

采用反推过来的算法:

5号表决时,形成的状态是:

1得到0个宝石,死

2得到0个宝石,死

3得到0个宝石,死

4得到0个宝石,死

5得到100个宝石,活,同意

原因:

不用讲了,能轮到5号表决当然他独吞了

但是也会与题目违背了,因为前面几个海盗都是傻瓜差不多

4号表决时,形成的状态是:

1得到0个宝石,死