故事：

船上有十個海盜，有一天，他們搶到了一箱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號：......

這樣當聰明的0號當頭目時，從0號9號獲得的黃金分別是：96,0,1,0,1,0,1,0,1,0

程序建模：

花了一個上午寫了段小程序，結果與預期符合，大家想下有沒有優(yōu)化空間。

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;
      //假設自己被殺后，繼任者的最優(yōu)選擇
      int[] goldNumEveryIfNext = goldNum(pirateNum - 1, privaeChiefNo + 1);
      //遍歷繼任者的最優(yōu)選擇，假如發(fā)現失意者(沒有分配到任何黃金)，就分配一斤黃金收買，獲取必需的投票數，從繼任者的繼任者開始算
      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)));
  }