强盗分赃有关问题的计算机求解

强盗分赃问题的计算机求解
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个元素的组合，算法伪代码如下：

填入强盗人数和金币数之后点击“分赃”按钮即可将所有的不重复的解列在界面下方的列表视图中。在列表视图的任意行上右击鼠标即可弹出快捷菜单，将已计算出结果导出到文件中或者将文件中的计算结果导入软件中。
上图中是本文计算出的20个强盗分20个金币的109315个不同解。
5.存在问题本文存在的问题首先是递推并枚举组合的计算复杂度为O(n!)，n为强盗人数，稍大一些就无法计算了。在Intel Centrino2 P7450(2.13GHz，双核)、2GB内存、Win7 Ulti 32位（.net 4.0）下，需要两个多小时和近200MB内存才能完成20个强盗分赃的求解。要进一步提高还需要找到不需要递推的算法，即使找不到也可以采用更好的枚举组合的算法。
其次，即使采用递推和枚举组合，在去重时也可以对已有解建立便于查询和插入的索引，提高查询的速度。
这些问题有待进一步研究解决。
附录主要代码：
/*** 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;        }    }}
引用或转载请注明原文，谢谢！

 

 

查看更多 下一篇