强盗分赃问题的计算机求解
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: bianhaoqiong@163.com
* 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;
}
}
}
引用或转载请注明原文，谢谢！
