海盗分赃难题
故事：
船上有十个海盗，有一天，他们抢到了一箱100斤的黄金，打算分赃（以斤为最小单位）。十个海盗从高到低分为10个等级，分配权在最高等级的海盗手里。他可以任意分配每个海盗的所得，但必须取得半数或半数以上的海盗（包括自己在内）的支持，否则他将被同伴处死。处死之后分配权将转移到下一个等级最高的海盗手里，当然，他也将面临同样艰难的选择。
假设和问题：
假定“每个海盗都是绝对理智的”，那么“海盗头子该提出怎样的分配方案才能够使自己的收益最大化？”
请先自己思考一段时间，不要看答案！
请先自己思考一段时间，不要看答案！
请先自己思考一段时间，不要看答案！！！
小样儿，想看了吧，先给个小提示吧！
这题的关键在于反向推理，化繁为简，分治解决。用的是类似于递归的思路。 十个海盗情况不好考虑，那么当只剩下两个海盗的情况呢，三个呢？注意题目，只要包括自己在内的半数或半数以上的海盗同意即可。
思路和方案：
从最后一个海盗开始，模拟每个海盗的小心思，排在前面的海盗，要考虑后面海盗的心思，这其实是一个递归过程：
10号：只要前面的都死翘翘，我独得黄金，不过当只剩下9号时，他必然要占有全部黄金，我啥都得不到。我一定不会支持9号。因此，只要9号以前的人给我一斤黄金，我就支持他。
9号： 8号如果当头目，只要给10号一斤黄金就可以收买他，我什么都得不到，因此，只要8号以前的人给我1斤黄金，我就支持他。
8号： 7号如果当头目，只要给9号一斤黄金，就可以收买他，我什么都得不到，因此，只要7号以前的人给我1斤黄金，我就支持他。
7号: 6号如果当头目，只要给8号、10号各一斤黄金，就可以收买他（因为如果6号死翘翘，7号就会占有分配权，他只要给9号一斤黄金即可，到时8、10号啥都得不到），我什么都得不到，因此，只要6号以前的人给我1斤黄金，我就支持他。
……
1号：......
这样当聪明的1号当头目时，从1号到10号获得的黄金分别是：96,0,1,0,1,0,1,0,1,0
程序建模：
花了一个上午写了段小程序，结果与预期符合，大家想下有没有优化空间。
public class PirateSpoil3 {
private static int goldNumSum = 100;
public static int[] goldNum(int pirateNum, int privaeChiefNo) throws Exception {
int votesGet = 1;
int goldLeft = 100;
int[] goldNumEveryOne = new int[10];
int votesNeed = 0;
if (pirateNum % 2 == 1) {
votesNeed = pirateNum / 2 + 1;
} else {
votesNeed = pirateNum / 2;
}
if (pirateNum >= 3) {
// 继任者总是倾向于neng死自己，这样他就会获得最大利益，因此继任者分配都是0
goldNumEveryOne[privaeChiefNo+1] = 0;
// 继任者的继任者将一无所获，因此，只要给他分配一斤黄金，便可收买他
goldNumEveryOne[privaeChiefNo +2] = 1;
//假设自己被杀后，继任者的最优选择
int[] goldNumEveryIfNext = goldNum(pirateNum - 1, privaeChiefNo + 1);
//遍历继任者的最优选择，假如发现失意者(没有分配到任何黄金)，就分配一斤黄金收买，获取必需的投票数，从继任者的继任者开始算
for(int i = privaeChiefNo + 2;i<=9;i++){
if (goldNumEveryIfNext[i]==0&&goldNumEveryOne[i]==0){
goldNumEveryOne[i]++;
votesGet++;
}
//获得必需投票数即可
if (votesGet >= votesNeed) {
break;
}
}
//计算海盗头子可获得的黄金数目
for(int j = privaeChiefNo+1;j<=9;j++){
goldLeft=goldLeft- goldNumEveryOne[j];
}
goldNumEveryOne[privaeChiefNo ] =goldLeft;
return goldNumEveryOne;
} else if(pirateNum==1){
goldNumEveryOne[privaeChiefNo ] = goldNumSum;
}else if(pirateNum==2){
goldNumEveryOne[privaeChiefNo ] = goldNumSum;
goldNumEveryOne[privaeChiefNo+1] = 0;
}
return goldNumEveryOne;
}
public static void main(String[] args) throws Exception {
int privateNumALL = 10;
int leftNum = 10;
System.out.println(JSON.toJSONString(goldNum(leftNum,privateNumALL-leftNum)));
}
十个海盗时的运行结果：
[96,0,1,0,1,0,1,0,1,0]
五个海盗时的运行结果：
[0,0,0,0,0,98,0,1,0,1]
看了这个结果，有没有感觉到在一个绝对理性和利己的社会，聪明老大的优势和继任者的压力。不过海盗之间不一定是孤立的，他们之间可能会相互欺骗和合作，这就不单单是一道题目了，而是现实社会的博弈，更加错综复杂。