海盗分金币问题及代码实现

看到一个非常有趣的问题：

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 + ", ");
            }
        }
    }

}