故事：
船上有十個(gè)海盜有勾，有一天修肠，他們搶到了一箱100斤的黃金，打算分贓（以斤為最小單位）恕出。十個(gè)海盜從高到低分為10個(gè)等級(jí)询枚，分配權(quán)在最高等級(jí)的海盜手里。他可以任意分配每個(gè)海盜的所得浙巫，但必須取得半數(shù)或半數(shù)以上的海盜（包括自己在內(nèi)）的支持金蜀，否則他將被同伴處死。處死之后分配權(quán)將轉(zhuǎn)移到下一個(gè)等級(jí)最高的海盜手里的畴，當(dāng)然渊抄，他也將面臨同樣艱難的選擇。
假設(shè)和問(wèn)題：
假定“每個(gè)海盜都是絕對(duì)理智的”丧裁，那么“海盜頭子該提出怎樣的分配方案才能夠使自己的收益最大化护桦？”
請(qǐng)先自己思考一段時(shí)間，不要看答案煎娇！
小樣兒二庵，想看了吧，先給個(gè)小提示吧
這題的關(guān)鍵在于反向推理逊桦，化繁為簡(jiǎn)眨猎，分治解決。用的是類(lèi)似于遞歸的思路强经。 十個(gè)海盜情況不好考慮睡陪，那么當(dāng)只剩下兩個(gè)海盜的情況呢，三個(gè)呢匿情？注意題目兰迫，只要包括自己在內(nèi)的半數(shù)以上的海盜同意即可。
思路和方案：
從最后一個(gè)海盜開(kāi)始炬称，模擬每個(gè)海盜的小心思汁果，排在前面的海盜，要考慮后面海盜的心思玲躯，這其實(shí)是一個(gè)遞歸過(guò)程：
10號(hào)：只要前面的都死翹翹据德，我獨(dú)得黃金鳄乏，不過(guò)當(dāng)只剩下9號(hào)時(shí)，他必然要占有全部黃金棘利，我啥都得不到橱野。我一定不會(huì)支持9號(hào)。因此善玫，只要9號(hào)以前的人給我一斤黃金水援，我就支持他。
9號(hào)： 8號(hào)如果當(dāng)頭目茅郎，只要給10號(hào)一斤黃金就可以收買(mǎi)他蜗元，我什么都得不到，因此系冗，只要8號(hào)以前的人給我1斤黃金奕扣，我就支持他。
8號(hào)： 7號(hào)如果當(dāng)頭目毕谴，只要給9號(hào)一斤黃金成畦，就可以收買(mǎi)他，我什么都得不到涝开，因此循帐，只要7號(hào)以前的人給我1斤黃金，我就支持他舀武。
7號(hào): 6號(hào)如果當(dāng)頭目拄养，只要給8號(hào)、10號(hào)各一斤黃金银舱，就可以收買(mǎi)他（因?yàn)槿绻?號(hào)死翹翹瘪匿，7號(hào)就會(huì)占有分配權(quán)，他只要給9號(hào)一斤黃金即可寻馏，到時(shí)8棋弥、10號(hào)啥都得不到），我什么都得不到诚欠，因此顽染，只要6號(hào)以前的人給我1斤黃金，我就支持他轰绵。
……
1號(hào)：......
這樣當(dāng)聰明的0號(hào)當(dāng)頭目時(shí)粉寞，從0號(hào)9號(hào)獲得的黃金分別是：96,0,1,0,1,0,1,0,1,0
程序建模：
花了一個(gè)上午寫(xiě)了段小程序，結(jié)果與預(yù)期符合左腔，大家想下有沒(méi)有優(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死自己，這樣他就會(huì)獲得最大利益液样，因此繼任者分配都是0
goldNumEveryOne[privaeChiefNo+1] = 0;
// 繼任者的繼任者將一無(wú)所獲振亮，因此巧还，只要給他分配一斤黃金，便可收買(mǎi)他
goldNumEveryOne[privaeChiefNo +2] = 1;
//假設(shè)自己被殺后坊秸，繼任者的最優(yōu)選擇
int[] goldNumEveryIfNext = goldNum(pirateNum - 1, privaeChiefNo + 1);
//遍歷繼任者的最優(yōu)選擇狞悲，假如發(fā)現(xiàn)失意者(沒(méi)有分配到任何黃金)，就分配一斤黃金收買(mǎi)妇斤，獲取必需的投票數(shù)，從繼任者的繼任者開(kāi)始算
for(int i = privaeChiefNo + 2;i<=9;i++){
if (goldNumEveryIfNext[i]==0&&goldNumEveryOne[i]==0){
goldNumEveryOne[i]++;
votesGet++;
}
//獲得必需投票數(shù)即可
if (votesGet >= votesNeed) {
break;
}
}
//計(jì)算海盜頭子可獲得的黃金數(shù)目
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)));
}
