看到一个非常有趣的问题：
5个海盗A、B、C、D、E抢得100枚金币，他们按顺序依次提方案：首先由A提出分配方案，然后5人表决，超过半数同意方案才被通过，否则他将被扔入大海喂鲨鱼，依此类推，假设这5人都非常聪明并且绝对的理性，严格遵守规则，并且足够残忍，在自己收益相同的情况下会选择杀更多人。最后他们的分配方案是怎样的？
我的推理过程：
这个问题如果顺着推，从5个人直接开始，会陷入“海盗都足够聪明，收益最大化、尽可能杀人”的逻辑泥潭，无法理清思路，但是如果逆推，就容易多了。
-
假设只剩2个海盗D、E：
D必死无疑，即使自己一块也不拿，E也投反对票投死他，因为E足够残忍，然后获得100金币。
分配方案：0-100 -
3个C、D、E：
D无论如何都要保证C不会被投死，否则只剩下两个的时候，自己也必死无疑，所以他可以接受一块金币也分不到。
分配方案：100-0-0 -
4个B、C、D、E：
C总是想要投死B的，投死他后自己就可以获得100金币。
D的话，他会想，如果投死B，那么自己得不到金币，如果自己获得1块，那就不投死B。
E会想，如果B死，那么自己只能得到0块，所以只要B分自己1块，就保住他。
分配方案：98-0-1-1 -
5个A、B、C、D、E：
B：必然会希望A死
C：如果A死，自己可以得到0块，所以给他1块才能得到他的投票
D、E：如果A死，他们每人都可以得到1块，而A必须要得到他们2人中的一张投票(因为给C1块比较划算)，所以给他们其中一个2块，另一个不给。
分配方案：97-0-1-2-0 或者 97-0-1-0-2
问题延伸：如果海盗数量不固定，金币数量也不固定，甚至金币比海盗还要少，要如何分？
作为程序员，这种问题必然是要用代码实现来获得更多的更一般的解决方案的，下面给出我的一个实现，目前只支持找出一种方案：
import java.util.HashSet;
import java.util.Set;
/**
* 问题描述：
* <p>
* M个海盗抢得N枚金币，他们按顺序依次提方案：
* 首先由第一个人提出分配方案，然后所有人一起表决，超过半数同意方案才被通过，否则他将被扔入大海喂鲨鱼，依此类推，
* 假设这M人都非常聪明并且绝对的理性，严格遵守规则，并且足够残忍，在自己收益相同的情况下会选择杀更多人。
* <p>
* 备注：本算法只找出一种解决方案就算完成
*/
public class PiratePuzzle {
//金币数量
private int coinCount = 100;
//海盗数量
private int pirateCount = 5;
public PiratePuzzle(int coinCount, int pirateCount) {
this.coinCount = coinCount;
this.pirateCount = pirateCount;
}
public int[] resolvePuzzle() {
return getDistribution(pirateCount);
}
/**
* 获取当前海盗数量下，对提出方案的海盗来说，其余海盗每人都得到满足的需求量
*
* @param currPirateCountTotal 当前的海盗数量
* @return 其余海盗每人都得到满足的需求量
*/
private int[] getDistribution(int currPirateCountTotal) {
if (currPirateCountTotal == 1) {
return new int[]{coinCount};
} else {
int minsufficient[] = getDistribution(currPirateCountTotal - 1);
// System.out.println("\n" + (currPirateCountTotal - 1) + "人时的方案:");
// for (int goldCount : minsufficient) {
// System.out.print(goldCount + ", ");
// }
return getDistributionByMin(minsufficient);
}
}
/**
* 获取在已知所有其他海盗的最小满足量时的最佳分配方案
*
* @param othersMinDistribution 已知所有其他海盗的最小满足量
* @return 分配方案
*/
private int[] getDistributionByMin(int[] othersMinDistribution) {
//总共需要的票数
int countToatal = (othersMinDistribution.length + 1) / 2 + 1;
int finalResolve[] = new int[othersMinDistribution.length + 1];
int others[] = findBestSolution(othersMinDistribution, countToatal - 1);
int othersSum = 0;
for (int i = 0; i < others.length; i++) {
finalResolve[i + 1] = others[i];
othersSum += others[i];
}
finalResolve[0] = coinCount - othersSum;
return finalResolve;
}
/**
* 从数组中找出指定个数的元素，使它们的和最小，然后将那些元素+1
* 待完善：本解法不考虑多种方案的情况，只找出一个方案
*
* @param array 待选择数组
* @param count 指定的元素个数
* @return +1之后的数组
*/
private int[] findBestSolution(int array[], int count) {
int minTest = 0;
int found = 0;
Set<Integer> indexSet = new HashSet<>();//保存被分配的海盗的坐标
while (found < count) {
for (int j = array.length - 1; j >= 0; j--) {
if (minTest == array[j]) {
found++;
indexSet.add(j);
}
if (found == count) {
break;
}
}
minTest++;
}
//将其余的都置为0
for (int i = 0; i < array.length; i++) {
if (!indexSet.contains(i)) {
array[i] = 0;
} else if (array[i] < coinCount) {
array[i] += 1;
}
}
return array;
}
public static void main(String[] args) {
PiratePuzzle pp = new PiratePuzzle(10, 25);
int solution[] = pp.resolvePuzzle();
if (solution[0] < 0) {
System.out.println("\n悲剧了，无论怎么分都是必死无疑！！！");
} else {
System.out.println("\n" + (solution.length) + "人时的方案:");
for (int goldCount : solution) {
System.out.print(goldCount + ", ");
}
}
}
}
网友评论