java - 联盟搜索算法

Question

我正在寻找一种用 C、C++、Python 或 Java 实现的算法，用于计算 n 个代理的获胜联盟集，其中每个代理都有不同的票数。我将不胜感激任何提示。谢谢!

Answer 1

换句话说，你有一个数组 X[1..n] ，并希望拥有它的所有子集 sum(subset) >= 1/2 * sum(X) ，对吧？

这可能意味着整个系列都符合条件。

之后，您可以删除任何元素 k有X[k] < 1/2 * sum(X) ，每个这样的联盟也可以作为答案。

之后，您可以继续一个一个地删除元素，当您达到总和的一半时停止。

这显然不是最有效的解决方案:您不想删除 k1=1,k2=2如果你已经尝试过 k1=2,k2=1 ——但我相信你能处理好。