考虑值为6的石头：
将值为6的石头分为两部分，一部分均分为两堆，另一部分用于填补缺口。
所谓填缺口就是当其他的石头分完之后再把这部分石头分入两堆(也有可能只放入一堆)。
现在考虑需要多少6值石头用于填缺口。
假设左边的总值小于右边的总值
1.要能均分，剩下的缺口一定是6的倍数;
2.在分配其他的石头时，可以做到尽可能的是缺口小
（比如，如果可以在右边找到几个石头使它们的值之和为6，可以把它们匀给左边）;
3.当不能再从右边匀给左边时，可能出现的缺口在大是多少？(缺口大小确定了就可以确定需要的用于填缺口的石头数量)
        缺口可能是30(右边刚好比左边多6个5值石头)
        缺口可能是是36？ 
        {要能产生36的缺口，需要在右边从值为1-5的石头中拿出几个使它们的总值不小于36，并且这几个石头匀不过去。
         2值石头不能超过2个（超过了可以匀一个6过去），3值石头不能超过1个（超过了可以匀一个6到左边），4值石头不能超过2个（超过了可以匀一个12到左边），5值石头不能超过5（超过了可以匀一个30到左边，缺口转移到右边为24<36），1值石头不能超过5个。
                1*5+2*2+3*1+4*2=20 36-20=16,5值石头至少需要3个;
                5值石头有3个：4值石头只能有1个(4+4+5+5=18 可以匀一个18到左边),不能有3值石头(3+5+5+5=18),凑不齐;
                5值石头有4个: 同样凑不齐;
                5值石头有5个: 同样凑不齐。
      }        
能得到的最小缺口不可能是36,因为总能匀几个石头使缺口小于36。

所以对于6值石头，最多需要5个来填缺口，其余均分即可。

对于其他值的石头，可以采用同样的分析;
值              需要用于填缺口的数量
1               6
2               5
3               5
4               5
5               6
6               5

统一一下
1               6
2               6
3               6
4               6
5               6
6               6

留下需要填补缺口的石头，把剩下的石头(偶数个)均分为两堆
需要考虑的也只是用来填缺口的石头。

if(marbles[i]>6){
        if(marbles[i]%2)
                marbles[i]=5;
        else marbles[i]=6;
}

• Re:一个剪枝想法, marbles个数超过6没有必要，截掉即可 (29) lnever1 2014-11-11 16:02:50