强盗分赃问题的计算机求解.pdfVIP

强盗分赃问题的计算机求解 RUC DB-IIR 卞昊穹 /bhq2010 2012/08/27 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 中选取一个以博得支持，即枚举C1个组合。实现过程中就需 2 要解决枚举Cr 个组合的问题。 n 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 个元素的组合，算法伪代码如下： 1 初始化数组a=[1,2,…,r] ，m=[n-r+1,n-r+2,…,n]; //数组的起始下标为1 2 while (a != m) //a 中的元素与m 的元素逐个对应比较，任一不相等则a!=m 3 { 4 output(a); //将数组a 所表示的组