1.問題描述
n個強盜（編號1,2,3,…,n）分贓m個金幣。先由強盜1提出分配方案，所有的強盜投票，超過半數支持則方案通過，否則將強盜1殺死、由強盜2繼續提方案，以此類推。假設所有的強盜都足夠聰明，並且有以下三個目的，優先級遞降，但互相之間不能達成協議：
1、盡可能保住自己的性命；
2、盡可能得到更多的金幣；
3、盡可能殺死更多的同伙。
試用計算機求解：強盜1應該采取怎樣的分配方案來保住性命並獲得最多的金幣？
2.問題分析
由於強盜是按照編號依次提出方案的，所以除了強盜n以外的強盜都有可能被殺死。由於所有的強盜之間不能有協議，故除了提出方案的強盜以外，其他的強盜都只會考慮如果殺死當前提出方案的強盜，下一個提方案者是否可以使自己獲得更多的金幣。所以最終問題遞歸到兩個強盜分金幣的情況，該情況下強盜1即使將金幣全部給強盜2，也會被殺死。
因此，兩個強盜分贓是沒有意義的，該問題的求解就變成了從三個強盜分贓方案逐步得到n個強盜分贓方案的問題。
n個強盜分贓時，強盜1的方案要通過，其余(n-1)個強盜中至少要有floor(n/2)個投支持票。實現時選擇遞推算法較遞歸更加節約時間空間，即從3個強盜分贓的方案逐步推出n個強盜分贓的方案。
在實現過程中，有兩個比較重要的問題：
1、枚舉組合
強盜1為了使自己獲得更多的金幣，需要選取“期望”金幣數的最少（即如果強盜1被殺死，下一輪中可能獲得金幣數最少）的floor(n/2)個強盜，給他們每個人多於“期望”一枚金幣以博得他們的支持。轉化為統計問題則為：將n-1個整數升序排列，取出所有小於第floor(n/2)個整數的整數（假設有x個），以及foor(n/2)-x個和第floor(n/2)個整數相等的整數。由於和第floor(n/2)個整數相等的整數的個數y大於等於foor(n/2)-x，故可能產生多個解。例如，當4個強盜分贓時只有m-2, 0, 1, 1（按照強盜編號升序排列，下同）一個解，當5個強盜分贓時，強盜1就需要從強盜4和5中選取一個以博得支持，即枚舉C_2^1個組合。實現過程中就需要解決枚舉C_n^r個組合的問題。
2、去重
n個強盜分贓可能有多個解，那麼n+1個強盜分贓時，n個強盜分贓時的每一個解都可能繼續產生到多個解，以此可得出n+1個強盜分贓的所有解，但這些解中有一些是重復的。例如，當7個強盜分贓時，有4個解：
m-4, 0, 1, 2, 0, 1, 0
m-4, 0, 1, 0, 0, 1, 2
m-4, 0, 1, 2, 0, 0, 1
m-4, 0, 1, 0, 0, 2, 1
由此可以得到8個強盜分贓時的8個解：
m-5, 0, 1, 2, 0, 1, 0, 1
m-5, 0, 1, 0, 0, 1, 2, 1
m-5, 0, 1, 2, 1, 1, 0, 0
m-5, 0, 1, 0, 1, 1, 2, 0
m-5, 0, 1, 2, 0, 1, 1, 0
m-5, 0, 1, 0, 0, 1, 1, 2
m-5, 0, 1, 2, 1, 1, 0, 0
m-5, 0, 1, 0, 1, 1, 0, 2
但是第3個和第7個是重復的。
這些重復的解必須去除，否則會使得之後的計算中產生很多不必要的時間空間消耗以及更多重復的解。
3.問題求解
計算過程中可以邊計算邊打表，這樣消耗一些內存空間但是可以從統計上減少重復的計算。例如計算20個強盜分贓方案時，將計算過程中得到的3-19個強盜的分贓方案都保存在內存中，之後如果要計算3-19個強盜的分配方案就可以直接從內存中讀出計算結果，計算大於20個強盜分贓的方案時也無需再計算3-20個強盜的分贓方案了。
上述的兩個問題解決如下：
枚舉組合問題可以用比較原始的算法。從1,2,…,n中選出r個元素的組合，算法偽代碼如下：
[cpp]
初始化數組a=[1,2,…,r]，m=[n-r+1,n-r+2,…,n]; //數組的起始下標為1
while (a != m) //a中的元素與m的元素逐個對應比較，任一不相等則a!=m
{
output(a); //將數組a所表示的組合輸出
for (i=r; i>0; --i)
{
if (a[i] < m[i])
{
a[i]++;
for (j=i+1; j <= r; ++j)
{
a[j]=a[j-1]+1;
}
break;
}
}
}
output(m);
去重問題沒有什麼好辦法，只能存儲已有的解，在得到一個新解時去查找是否存在相同的已有解。為了提高查找的速度，可以建立索引（當17個強盜分贓時就有上萬個解，所以建立索引是很有必要的，但插入時也需要更新索引的代價，故要選擇合適的索引），但本文簡單起見就采用了線性的查找，找到一個相同的已有解時查找結束，否則將遍歷所有的已有解。
4.編程實現
雖然2個強盜分贓沒有意義，但本文在編程實現時還是認為2個分贓時，強盜1可以承諾以後付給強盜2額外的一枚金幣以報不殺之恩（雖然這違背了強盜之間不能達成協議的約束條件），故程序中2個強盜分贓的方案是-1, m+1，而1個強盜分贓的方案就是m。這麼做只是我一時頭腦發熱而已。另外代碼中不小心把強盜的編號弄反了，即讓編號大的強盜先提方案，不過不影響結果。
用C#在VS2010上編程實現了n個強盜分贓的求解，代碼見附錄。界面截圖如下：
填入強盜人數和金幣數之後點擊“分贓”按鈕即可將所有的不重復的解列在界面下方的列表視圖中。在列表視圖的任意行上右擊鼠標即可彈出快捷菜單，將已計算出結果導出到文件中或者將文件中的計算結果導入軟件中。
上圖中是本文計算出的20個強盜分20個金幣的109315個不同解。
5.存在問題
本文存在的問題首先是遞推並枚舉組合的計算復雜度為O(n!)，n為強盜人數，稍大一些就無法計算了。在Intel Centrino2 P7450(2.13GHz，雙核)、2GB內存、Win7 Ulti 32位（.net 4.0）下，需要兩個多小時和近200MB內存才能完成20個強盜分贓的求解。要進一步提高還需要找到不需要遞推的算法，即使找不到也可以采用更好的枚舉組合的算法。
其次，即使采用遞推和枚舉組合，在去重時也可以對已有解建立便於查詢和插入的索引，提高查詢的速度。
這些問題有待進一步研究解決。
附錄
主要代碼：
[csharp]
/**
* author: Solari
* email: [email protected]
* 2012.8.27
*/
using System;
using System.Collections;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.IO;
namespace SpoilsDivider
{
public partial class Form_Main : Form
{
public Form_Main()
{
InitializeComponent();
}
private ArrayList finished = null;
private static int CoinNum = 20;
private ArrayList DoDivide(int robberNum)
{
ArrayList pre = null;
if (finished == null)
{
//如果第1次進行計算
finished = new ArrayList();
pre = new ArrayList();
ArrayList tmp = new ArrayList();
tmp.Add(new Robber(1, CoinNum));
pre.Add(tmp);
finished.Add(pre);
if (robberNum == 1)
{
return pre;
}
}
else if (finished.Count >= robberNum)
{
//如果已有計算結果
return (ArrayList)(finished[robberNum - 1]);
}
else
{
//如果有1個較接近的計算結果
pre = (ArrayList)finished[finished.Count - 1];
}
for (int i = finished.Count; i < robberNum; ++i)
{
//已有若干組i個強盜的分配方案
ArrayList tmppre = new ArrayList();
foreach (Object obj in pre)
{
//已有1組i個強盜的分配方案
ArrayList preres = (ArrayList)obj;
DoNexRes(ref tmppre, preres, i);//產生下一個強盜的分配方案添加tmppre中
}
pre = tmppre;
finished.Add(pre);
}
return pre;
}
private void button_Divide_Click(object sender, EventArgs e)
{
try
{
int robberNum = int.Parse(textBox_RobberNum.Text);
CoinNum = int.Parse(textBox_CoinNum.Text);
if (robberNum <= 20 && robberNum >= 3)
{
ArrayList results = DoDivide(robberNum);
int i = 0;
listView_DivideRes.Items.Clear();
foreach (Object obj in results)
{
ArrayList result = (ArrayList)obj;
ListViewItem item = new ListViewItem((++i).ToString());
String str = "";
foreach (Object obj2 in result)
{
str += ((Robber)obj2).coins.ToString() + ",";
}
item.SubItems.Add(str.Substring(0, str.Length-1));
listView_DivideRes.Items.Add(item);
}
}
else
{
throw new Exception("強盜人數須在[3, 20]之間");
}
}
catch (Exception err)
{
MessageBox.Show(err.Message);
}
}
private void DoNexRes(ref ArrayList temppre, ArrayList preres0, int i)
{
int sum = 0;//分給別的強盜的金幣數
ArrayList preres = new ArrayList();
foreach (Object obj in preres0)
{
Robber ro = new Robber(((Robber)obj).id, ((Robber)obj).coins);
preres.Add(ro);
}
preres.Sort(new RobberCoinsCom());
int j = (i + 1) / 2;
int midCoins = ((Robber)preres[j - 1]).coins;
int s = j - 1, d = j;
for (int k = j - 2; k >= 0; --k)
{
if (((Robber)preres[k]).coins < midCoins)
{
s = k + 1;
break;
}
}
for (int k = j; k < i; ++k)
{
if (((Robber)preres[k]).coins > midCoins)
{
d = k;
break;
}
}
for (int k = 0; k < s; ++k)
{
((Robber)preres[k]).coins++;
sum += ((Robber)preres[k]).coins;
}
int n = d - s, r = j - s;
int[] a = new int[r + 1];
int[] m = new int[r + 1];
for (int k = 1; k <= r; ++k)
{
a[k] = k;
m[k] = n - r + k;
}
int sum1 = sum, L = 0;
ArrayList preres1 = new ArrayList();
foreach (Object obj in preres)
{
Robber ro = new Robber(((Robber)obj).id, ((Robber)obj).coins);
preres1.Add(ro);
}
for (int k = s; k < s+r ; ++k)
{
((Robber)preres1[k]).coins++;
sum1 += ((Robber)preres1[k]).coins;
}
for (int k = s + r; k < i; ++k)
{
((Robber)preres1[k]).coins = 0;
}
preres1.Add(new Robber(i + 1, CoinNum - sum1));
preres1.Sort(new RobberIdCom());
bool exist = false;
foreach (Object obj in temppre)
{
if (resEqual(preres1, (ArrayList)obj, i + 1))
{
exist = true;
break;
}
}
if (!exist)
{
temppre.Add(preres1);
}
while (!isMax(a, m, r))
{
sum1 = sum;
L = 0;
for (int k = r; k > 0; --k)
{
if (a[k] < m[k])
{
a[k]++;
L = a[k] + 1;
for (int p = k + 1; p <= r; p++)
{
a[p] = L;
L++;
}
break;
}
}
preres1 = new ArrayList();
foreach (Object obj in preres)
{
Robber ro = new Robber(((Robber)obj).id, ((Robber)obj).coins);
preres1.Add(ro);
}
for (int p = 1; p <= r; ++p)
{
for (int k = s; k < d; ++k)
{
if (k == a[p] + s - 1)
{
((Robber)preres1[k]).coins++;
sum1 += ((Robber)preres1[k]).coins;
}
else
{
((Robber)preres1[k]).coins = 0;
}
}
}
for (int k = d; k < i; ++k)
{
((Robber)preres1[k]).coins = 0;
}
preres1.Add(new Robber(i + 1, CoinNum - sum1));
preres1.Sort(new RobberIdCom());
exist = false;
foreach (Object obj in temppre)
{
if (resEqual(preres1, (ArrayList)obj, i + 1))
{
exist = true;
break;
}
}
if (!exist)
{
temppre.Add(preres1);
}
}
}
private bool isMax(int[] a, int[] m, int r)
{
bool flag = true;
for (int i = 1; i <= r; ++i)
{
if (a[i] < m[i])
{
flag = false;
break;
}
}
return flag;
}
private bool resEqual(ArrayList l1, ArrayList l2, int len)
{
bool res = true;
for (int i = 0; i < len; ++i)
{
if (((Robber)l1[i]).coins != ((Robber)l2[i]).coins)
{
res = false;
break;
}
}
return res;
}
public partial class Robber
{
public Robber(int i, int c)
{
id = i;
coins = c;
}
public int id;
public int coins;
}
public partial class RobberIdCom : IComparer
{
public int Compare(object x, object y)
{
return ((Robber)y).id - ((Robber)x).id;
}
}
public partial class RobberCoinsCom : IComparer
{
public int Compare(object x, object y)
{
if (((Robber)x).coins == ((Robber)y).coins)
{
return ((Robber)y).id - ((Robber)x).id;
}
return ((Robber)x).coins - ((Robber)y).coins;
}
}
}
引用或轉載請注明原文，謝謝！
