学步园

本文用递归方法解决一个智力题。题目如下：5个强盗分100个金币，如果第一个人提出的分配方案得到半数以上（含半数）的人同意则执行，否则处死第一个人，再由第二个人提出方案，直到分配完成。第一个人提出怎样的方案才能既获得最大利益又没有杀身之祸？这里假设每个人都是理性的且追求最大的利益。

    第1个人提出的分配方案要满足两个条件，一是得到半数以上的人支持。二是使自己获得最大的利益。为了取得别人的支持需要给他们部分利益，显然这部分利益要超过他们在第2个人提出的可接受分配方案中所获得的利益。如果不这样，他们会反对，从而接受第2个人提出的方案。
    问题变成了求第2个人提出的可接受方案。他的方案也要满足上面的两点。以此类推，问题变成最后一个人提出可接受方案，显然可以提可接受的方案，因为没有人反对，把金币全部分给自己。

下面是他们的方案：
第5个人的方案：0，0，0，0，100。（不需要别人的支持）
第4个人的方案：0，0，0，100，0。（不需要别人的支持）
第3个人的方案：0，0，99，0，1。（第5个人会支持他）
第2个人的方案：0，99，0，1，0。（第4个人会支持他）
第1个人的方案：98，0，1，0，1。（第3，5个人会支持他）

    从分析中可得，这个问题可以用递归求解，把求n个人的分配问题变成求n-1个人的分配，实现代码如下。

#include <vector>

// 得到最大利润分配
// 输入参数：people有多少个人分配
// 输入参数：gold有多少金币
// 输出参数：p_get分别方案
void GetMaxProfits(int people, int gold, std::vector<int>& p_get)
{
    // 除去自己,还需要得到多少人的支持
    int vote = (people+1)/2-1;
//    int vote = people/2;

    if (vote > 0)    // 需要其他人的支持
    {
        // 得到people-1个人数的最佳分配方案
        GetMaxProfits(people-1, gold, p_get);

        // 计算为了得到vote人数的支持，需要让出多少利益
        int min = gold+1;    // 需要让出的利益，初始为一个较大的数
        std::vector<int> tmpset(vote, 0);;    // 记录给哪些人让利

        // 找出得到较少利益的vote个人
        for (int i=0, c=0; i<people-1 && c<vote; i++)
        {
            int seq = 0;
            for (int j=0; j<people-1; j++)
            {
                if (p_get[i] > p_get[j])
                    seq++;
            }
            if (seq < vote)
            {
                tmpset[c++] = i;
            }
        }

        // 记录需要让利的人在people-1情况下的利益
        std::vector<int> voteprofit(vote, 0);
        for (int i=0; i<tmpset.size(); i++)
            voteprofit[i] = p_get[tmpset[i]];

        // 不需要让利的人分配0个金币
        for (int i=0; i<people-1; i++)
            p_get[i] = 0;

        // 给需要让利的人分配金币
        int surplus = gold;    // 还有多少可分配的
        for (int i=0; i<tmpset.size(); i++)
        {
            p_get[tmpset[i]] = voteprofit[i];
            surplus -= voteprofit[i];
            if (surplus > 0)    // 有余额多分配一个
            {
                p_get[tmpset[i]]++;
                surplus--;
            }
            else
                break;
        }

        // 自己的利益
        p_get[people-1] = surplus;
    }
    else        // 不需要其他人的支持
    {
        for (int i=0; i<people-1; i++)
            p_get[i] = 0;
        p_get[people-1] = gold;
    }
}

int main(void)
{
    int gold;
    int people;
    printf("Input gold, people:");
    scanf("%d,%d", &people, &gold);

    std::vector<int> p_get(people, 0);
    GetMaxProfits(people, gold, p_get);
    
    for (int i=0; i<people; i++)
        printf("%d\t",p_get[i]);
    
    return 0;
}

        这道题的答案有些让人吃惊，本以为第一个人最危险，反而能获得较大利益。问题出在题目的假设：每个人都是理性的且追求最大的利益，从而低估了生命的价值。