algorithm - 不同组合算法(糖果分割)

昨天我参加了Google Code Jam竞赛。有那个糖果 split 的问题。
http://code.google.com/codejam/contest/dashboard?c=975485#s=p2

我设计了一种算法，该算法基本上会针对Patrick的桩和Sean的桩尝试所有不同的组合，检查它们是否具有相同的Patrick值，最后选择可使Sean所占份额最大化的组合。该算法适用于小的输入文件。对于大型服务器，我遇到了内存问题，并且输出从未显示出来。我相信有另一种方法可以解决这个问题，而无需考虑所有组合。有人可以帮忙吗？

最佳答案

对于较小的输入，糖果的数量很小(最多15个)。搜索所有可能的情况将由2 ^ 15 = 32768个可能性组成，可以在毫秒左右的时间内进行检查。但是，对于多达1000个糖果(大输入)，可能的组合数量最多为2 ^ 1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376。现在这个数字太大了，即使您运行该程序几年，也不会得到结果。

有一些观察意见有助于为此制定有效的程序:

就像@Protostome指出的那样，Patrick的和实际上是xor运算的和。

再次像@Protostome指出的那样，如果可求解，则所有糖果的异或将为0。原因是:如果两个分区中的异或总和相同，则对两个分区进行异或。将是a xor a = 0。

如果可以分区，则所有糖果的异或为0。但是，如果我们从整个糖果集合中删除单个糖果，则它变为非零。特别是

。

   c1 xor c2 xor ... xor ci-1 xor ci xor ci+1 xor ... xor cn = 0
=> c1 xor c2 xor ... xor ci-1     xor    ci+1 xor ... xor cn = ci

也就是说，我们可以通过从整个集合中取出一个糖果来将集合分成两部分。为了使左半部分的算术总和最大化，我们必须取最低值的糖果。因此，较高桩中的糖果的算术总和是所有糖果的总和-最低值!

因此，我们有:

如果所有糖果的异或为零，则可解决

如果可解决，则总和是整个列表的总和-最小值。