java - 是否有可能在相对较短的时间内在一个程序中找到所有可能的选举学院并列组合？

Question

我的计算机科学老师把这个问题布置给了我们，我们类几乎每个人都对这个问题的复杂性大喊大叫。我们只是在高中学习计算机科学的高级主题，我们都不知道从哪里开始，使用什么算法或任何东西。我们已经确定，直接通过每一种可能的组合，将有 2^50 种组合可以运行，这对于我们任何人来说都是非常大的搜索方式。我只是很好奇这是否有可能在我们较低的计算机科学技能水平下完成，是否有人个人认为这是一个公平的问题，因为我们的老师仍然没有找到解决他自己问题的方法。谢谢!

Answer 1

解空间实际上不是 2^50。平局(假设只有两名候选人)意味着 269-269。你不能只有一个州(甚至只有少数几个州)才能达到 269，所以你可以立即扔掉所有小子集和所有大子集(赢得每个州也行不通)。此外，您只需查找总数为 269 的子集(因为总共有 538 个，这意味着每个集合的补集也是 269)。

也就是说，这仍然归结为子集和问题:( https://en.wikipedia.org/wiki/Subset_sum_problem ) 因此任何解决方案都无法很好地扩展(除非您弄清楚如何在多项式时间内完成，在这种情况下您可以 claim 1,000,000 美元)。但是，您的问题不是扩展它；对于美国选举人团配置的情况(包括某些州的投票 split )，在合理的时间内(如您所说，< 10 分钟)计算出来的时间并不算太大。