不同组合算法（糖果分配）

Question

昨天我参加了Google代码杯比赛。其中有一个糖果分割问题。 http://code.google.com/codejam/contest/dashboard?c=975485#s=p2 我设计了一个算法，基本上尝试了所有不同的Patrick堆和Sean堆的组合，检查它们是否具有相同的Patrick值，并最终选择能够最大化Sean份额的组合。该算法在小输入文件中表现良好。但对于大文件，我遇到了内存问题，输出从未出现。我相信必须有另一种方法来解决这个问题，不需要考虑所有组合。有人能帮忙吗？

- Keeto

Answer 1

对于小输入，糖果数量较少（最多15颗）。检索所有可能的情况会产生2^15 = 32768种可能性，可以在一毫秒左右内进行检查。但对于多达1000颗糖果（大输入），可能的组合数增加到2^1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376。现在这个数字有点太大了，即使运行几年，也无法得出结果。

以下是有助于制作有效程序的一些观察结果：

• 像@Protostome指出的那样，Patrick的总和实际上是一个异或操作。
• 再次像@Protostome指出的那样，如果可以解决，则所有糖果的异或值将为0。原因是这样的：如果可以在两个分区中具有相同的异或和，则将两个分区的异或和取XOR将得到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. 如果可解决，总和为整个列表的总和减去最低值。

- Raze

---

哇，我真后悔自己只意识到每个值的第i位之和需要是偶数这一点就足以成功解决大问题了，但我没有意识到可以直接对所有值进行异或运算，而不是找到每个位的总和的奇偶性！唉！ - Robin Green