題意

P個海盜偷了D顆鉆石后分贓（$3 leq P, Dleq 100$），采用分贓策略：

從1號開始，提出一個分配金幣的方案，如果能夠得到包括1號在內(nèi)的絕對多數(shù)（即大于半數(shù)）同意，則執(zhí)行該方案，否則1號將被投入大海喂鯊魚；而后依次類似地由第2號、第3號等等海盜提方案。

且有假設(shè)：1.絕頂聰明，總以個人利益最大化作為行為準則；2.在能夠取得盡量多鉆石的情況下，海盜不會故意致同伙于死地；

分析

倒著分析，

假設(shè)一種普通的情況，10顆鉆石7個人分。

如果只剩2個人，那么無論2說什么1都會反對，除非他把鉆石全給他。也就是下面這種情況。

（0，10）

如果只剩3個人，3知道了如果自己死了2的處境，如果想讓自己的提議實現(xiàn)只要爭取1個人的同意就好了。所以3會給2號一顆鉆石2就會同意3的提議,不然就一枚都拿不到了。這樣就變成了：

（9，1，0）

如果只剩4個人，4知道了如果自己死了3的方案，如果想讓自己的提議實現(xiàn)只要爭取2個人的同意就好了。所以4會給2號多一顆鉆石，給1號一顆鉆石，1和2就會同意4的提議。這樣就變成了：

（7，0，2，1）

如果只剩5個人，5知道了如果自己死了4的方案，如果想讓自己的提議實現(xiàn)只要爭取2個人的同意就好了。所以5會給3號一顆鉆石，給1號2顆鉆石。這樣就變成了：

（7，0，1，0，2）

如果只剩6個人，6知道了如果自己死了5的方案，如果想讓自己的提議實現(xiàn)只要爭取3個人的同意就好了。所以6會給4，2號一顆鉆石，給3號2顆鉆石。這樣就變成了：

（6，0，1，2，1，0）

現(xiàn)在我們可以推出7個人的情況了，7知道了如果自己死了6的方案，如果想讓自己的提議實現(xiàn)只要爭取3個人的同意就好了。所以7會給4，2號一顆鉆石，給3號2顆鉆石。這樣就變成了：

（6，0，1，2，0，0，1）

總結(jié)一下就是，有$i$ 個人時，由于知道 $i-1$ 個人時的情況，所以在前一輪選最小的 $i/2$ 個并每個多給一個。

具體的規(guī)律是 $P > 3$ 時，總有 $i/2-1$ 個1和一個2；$p=3$ 時為 $(D-1 1 0)$.

代碼實現(xiàn)應該很簡單吧.略

參考鏈接：http://www.voidcn.com/article/p-cxovyfju-qm.html

總結(jié)

以上是生活随笔為你收集整理的浙大PAT 2-10. 海盗分赃——经典博弈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。