algorithm - 不同的组合算法(糖果 split )

Question

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

我设计了一种算法，该算法基本上会尝试 Patrick 的堆和 Sean 的堆的所有不同组合，检查它们是否具有相同的 Patrick 值，最后选择能够最大化 Sean 份额的组合。该算法适用于小输入文件。对于大的，我遇到了内存问题并且输出从未出现过。我相信有另一种方法可以解决这个问题，不需要考虑所有组合。谁能帮忙？

Answer 1

对于小输入，糖果的数量很少(最多 15 个)。对所有可能情况的搜索将包含 2^15 = 32768 种可能性，可以在一毫秒左右的时间内进行检查。 But with upto 1000 candies (large input), the number of possible combinations go upto 2^1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376.现在这个数字有点太大了，即使你运行这个程序几年，你也不会得到结果。

有一些观察结果有助于为此制定一个有效的程序:

• 就像@Protostome 指出的那样，Patrick 的求和实际上是一个异或运算。
• 再次像@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

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

因此，我们有:

1. 如果所有糖果的异或为零，则可解
2. 如果它是可解的，则总和是整个列表的总和 - 最低值。