代码重现海盗分金问题分析过程
有五个理性的海盗,A, B, C, D和E,找到了100个金币,需要想办法分配金币。
海盗们有严格的等级制度:A比B职位高,B比C高,C比D高,D比E高。
海盗世界的分配原则是:等级最高的海盗提出一种分配方案。所有的海盗投票决定是否接受分配,包括提议人。并且在票数相同的情况下,提议人有决定权。如果提议通过,那么海盗们按照提议分配金币。如果没有通过,那么提议人将被扔出船外,然后由下一个最高职位的海盗提出新的分配方案。
海盗们基于三个因素来做决定。
首先,要能存活下来。
其次,自己得到的利益最大化。
最后,在所有其他条件相同的情况下,优先选择把别人扔出船外。
#encoding=utf-8 N = 500 #海盗个数 M = 100 #金子个数 last = [M] # 一个人分得M个金子 for rem in range(1, N): #print(rem, ": ", last[-1]) print(rem, last[-1:0:-1]) # 当前有 rem 个海盗的分金方法 #rem-1个海盗的分金办法,按分得的金子排序, 截取前一半 tmp = sorted([(i, last[i]) for i in range(len(last))], cmp =lambda x, y: cmp(x[1],y[1])) remain = M # 当前分配方式剩余 remain 个金子 cur = [0 for i in range(rem+1)] for (i, gold) in tmp[0:rem/2]: cur[i] = gold+1 remain -= gold+1 cur[rem] = remain if cur[rem]<0: # 如果是必死,则分配方案不变 last.append(-1) else: last = cur
输出
(1, []) (2, [100]) (3, [99, 0]) (4, [99, 0, 1]) (5, [98, 0, 1, 0]) (6, [98, 0, 1, 0, 1]) (7, [97, 0, 1, 0, 1, 0]) (8, [97, 0, 1, 0, 1, 0, 1]) (9, [96, 0, 1, 0, 1, 0, 1, 0]) (10, [96, 0, 1, 0, 1, 0, 1, 0, 1])#学习路径##Java#