我正在寻找一种用 C、C++、Python 或 Java 实现的算法,用于计算 n 个代理的获胜联盟集,其中每个代理都有不同的票数。我将不胜感激任何提示。谢谢!
最佳答案
换句话说,你有一个数组 X[1..n]
,并希望拥有它的所有子集 sum(subset) >= 1/2 * sum(X)
,对吧?
这可能意味着整个系列都符合条件。
之后,您可以删除任何元素 k
有X[k] < 1/2 * sum(X)
,每个这样的联盟也可以作为答案。
之后,您可以继续一个一个地删除元素,当您达到总和的一半时停止。
这显然不是最有效的解决方案:您不想删除 k1=1,k2=2
如果你已经尝试过 k1=2,k2=1
——但我相信你能处理好。
关于java - 联盟搜索算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8019172/