海盗分赃难题

故事：

船上有十个海盗，有一天，他们抢到了一箱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]

看了这个结果，有没有感觉到在一个绝对理性和利己的社会，聪明老大的优势和继任者的压力。不过海盗之间不一定是孤立的，他们之间可能会相互欺骗和合作，这就不单单是一道题目了，而是现实社会的博弈，更加错综复杂。

java达人

ID：drjava

（长按或扫码识别）