代码重现海盗分金问题分析过程

有五个理性的海盗，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])