0. 写作目的

有趣的编程。

1. 问题描述

有n个海盗，分k个金币。

分配原则：依次从第一个人到最后一个人提出分配方法，只有当超过半数的人同意时，方案生效。如果该人提出的方案不能生效，则该人会被扔到水里喂鱼。游戏只能玩一次。问：第一个人如何提出分配方案才能最大化自己的利益？

假设：1) 所有的海盗都很聪明，而且理智；

           2) 人性本恶（如当只有两个人时，无论第一个人如何分配，即使第一个不要金币，第二个人都不同意第一个的分配方案，则第一个人必死。）

           3) 每个海盗在获取自己最大利益时，会采用赌博心理，即最大化可能得到的金币数目

2. 实例问题分析

先从简单的问题分析： 假设金币有100个。

当n = 1时，所有金币都是第一个人的。

当n = 2时，第一个人0个金币，第二个人100个金币。（因为无论第一个人如何分配，只要第二个人不同意，则第一个人必死。）

当n = 3时，第一个人100个金币，第二个人0个金币，第三个人0个金币。（由于第二个人知道如果第一个人死了，则第二个人也必死，因此第二个人必须同意第一个人的分配方案。这件事情第一个人也是知道的，因此第一个人可以任意分配。）

当n = 4时，第一个人98个金币，第二个人0个金币，第三个人1个金币，第四个人1个金币。（第一个人知道如果自己死了，每个人金币的分配情况。因此第一个人不能拉拢第二个人，也拉拢不来。第一个人需要拉拢的是第三个人和第四个人，因此只要他们的金币优于当n = 3时的分配情况，第三个人和第四个人就会同意第一个人的分配方案。）

当n = 5时，第一个人97个金币，第二个人0个金币，第三个人1个金币，第四个人2个金币，第五个人0个金币。（或者第四个人0个金币，第五个人2个金币）（第一个人知道当n = 4时金币分配的情况，由于需要半数，因此需要拉拢2个人。首先第二个人肯定拉拢不过来，需要拉拢的是第三个人，给1个金币，第四个人给2个金币第5个人0个金币，或者第5个人给2个金币，第4个人0个金币。）

依次类推......

我们来看一下，当金币的数目为10的情况。

当n = 1时，所有金币都是第一个人的。

当n = 2时，第一个人0个金币，第二个人10个金币。

当n = 3时，第一个人10个金币，第二个人0个金币，第三个人0个金币。

当n = 4时，第一个人8个金币，第二个人0个金币，第三个人1个金币，第四个人1个金币。

当n = 5时，第一个人7个金币，第二个人0个金币，第三个人1个金币，第四个人2个金币，第五个人0个金币。（当存在多种情况的时候，这里只讨论第一种可能的情况，但是这并不意味这后面的人不需要考虑了，后面会看到。）

当n = 6时，第一个人4个金币，第二个人0个金币，第三个人1个金币，第四个人2个金币，第五个人3个金币，第六个人0个金币。也可能是第五个人0个金币，第六个人3个金币。为什么第六个人是3个金币，因为从历史来看，当n =5时，第四个人或者第五个人都有可能是2个金币，因此如果想要拉拢这里的第五个人或者第六个人，只能出3个金币。

当n = 7时，第一个人4个金币，第二个人0个金币，第三个人1个金币，第四个人2个金币，第五个人3个金币，第六个人0个金币，第七个人0个金币。（这里第6、第7个人必定为0）

当n = 8时，第一个人5个金币，第二个人0个金币，第三个人1个金币，第四个人2个金币，第五个人0个金币，第六个人0个金币，第七个人1个金币，第八个人1个金币。

当n = 9时，第一个人5个金币，第二个人0个金币，第三个人1个金币，第四个人2个金币，第五个人0个金币，第六个人1个金币，第七个人1个金币，第八个人0个金币、第九0个金币（其中第4，第8，第9其中一个必为2个金币）。

结论：我们可以看到，在n个人中，第二个人是拉拢不来的，可以拉拢的是从第三个人开始往后的 个人，只要优于在n-1个人时的分配方案，第一个人的分配方案即可通过。这就是我们所说的“先手优势”。

但是“先手优势”会一直保存吗？如果人数很大，金币数目很少呢？

我们来举个特例，当 金币数目k = 1时，

当n = 1时， 第一个人1个金币。

当n = 2时，第一个人必死，第二个人1个金币。

当n = 3时，第一个人1个金币， 第二个人0个金币， 第三个人0个金币。

当n = 4时，第一个人必死，退化为n = 3。（因此如果拉拢第三，第四个人，需要2个金币，而金币数目只有1个，而且人性本恶，所以第一个人必死）。

当 n = 5时，情况又出现了转机。

总结：我们可以讨论在给定金币数目下，如果第一个人保持“先手优势”（定义“先手优势”：自己获取的利益大于其他所有人的和）时，最大的人数。这样就不会出现第一个必死的情况。

3. 抽象问题分析

从上述实例问题分析可以看出，如果考虑边界条件很复杂，这里只考虑“保持先手”优势的情况。

具体的求解过程可以为：

前n = 1, 2, 3时边界条件。当n > 3时，可以这样认为：将n -1时刻的记录下来，先将每一个都 加1，然后对这个n -1个数进行从小到大排序，去前个人，然后比较低个人的值是否存在于后续的值，如果存在则将后续相同的值作为同等考虑的范围，如果不存在相同的值，则后续的金币数都置为0。然后对于第一个人的金币，通过记录第的金币数目以及与它相等的人数，通过总金币数目减去拉拢人所需要的数目，如果第一个人的金币数目小于0，则说明第一个人必死，此时返回n -1个人的策略。

4. 代码（python）

说明：这里给出的是考虑第一个保持“先手优势”的情况。这里输出的不是可能的策略，输出的是当前策略中，拉拢半数人时可能的代价，但第一个人的金币数是正确的。

#!/usr/bin/env python
# _*_ coding:utf-8 _*_


def mySortDataIndex( dataList ):

    sortedDataIndexList = []
    sortedDataList = sorted( dataList.copy() )

    for i in range(0, len(sortedDataList) ):
        for j in range(0, len(sortedDataList)):
            if( dataList[j] == sortedDataList[i] ):
                sortedDataIndexList.append( j )
                dataList[j] = -1
                break
    return sortedDataIndexList

def Policy(n, k):
    if n == 1:
        return [k]
    elif n == 2:
        return [0, k]
    elif n == 3:
        return [k, 0, 0]
    else:
        historyPolicyList = Policy(n - 1, k)
        curPolicyList = []
        curPolicyList.append(0)
        tempPolicyList = []
        for data in historyPolicyList:
            tempPolicyList.append( data + 1 )
        sortedIndex = mySortDataIndex( tempPolicyList.copy() )
        #print( sortedIndex )

        if n % 2 == 0:
            half_n = int( n / 2 )
        else:
            half_n = int( (n - 1) / 2 )
        curOutputIndexList = []
        curOutputIndexList.append( 1 )

        copyNumber = 0
        copyValue = 0
        for ii in range( half_n, len( sortedIndex ) ):
            if( tempPolicyList[ sortedIndex[ii] ] == tempPolicyList[ sortedIndex[half_n - 1] ] ):
                copyNumber += 1
                copyValue = tempPolicyList[ sortedIndex[half_n - 1] ]
                continue
            else:
                tempPolicyList[ sortedIndex[ii] ] = 0

        temSum = 0
        for ii in range(0, len(tempPolicyList) ):
            temSum += tempPolicyList[ii]
            curPolicyList.append( tempPolicyList[ii] )
        temSum = temSum - copyNumber * copyValue



        #if (k - temSum) < 0:
         #   return historyPolicyList
        curPolicyList[0] = int(k - temSum)
        if curPolicyList[0] <= temSum:
            return historyPolicyList
        return curPolicyList



def main(n=5, k=10):
    policyList = Policy(n, k)
    return policyList




if __name__ == "__main__":
    k = 2
    for n in range(1, 20, 1):
        policyList = main(n, k)
        print( "n = {}, k = {}".format( n, k ) )
        for ii in range( len(policyList) ):
            if(ii != len(policyList) - 1):
                print("t {}".format(policyList[ii]), end="t")
            else:
                print("t {}".format( policyList[ii] ))

There may be some mistakes in this blog. So, any suggestions and comments are welcome!