相关疑难解决方法(0)

在对我在这里的原始问题进行了大量讨论后，我为贪婪的集封面想出了以下实现。从我得到的帮助，我编码的问题转化为“贪婪的集合覆盖”，并得到了一些更多的帮助后，在这里，我想出了下面的实现。我感谢所有帮助我解决这个问题的人。以下实现工作正常，但我想使其可扩展/更快。

通过可扩展/更快，我的意思是说：

• 我的数据集在 S 中包含大约 50K-100K 集
• U 本身的元素数量非常少，在 100-500 的数量级
• S 中每个集合的大小可以是 0 到 40

这是我的尝试：

U = set([1,2,3,4])
R = U
S = [set([1,2]), 
     set([1]), 
     set([1,2,3]), 
     set([1]), 
     set([3,4]), 
     set([4]), 
     set([1,2]), 
     set([3,4]), 
     set([1,2,3,4])]
w = [1, 1, 2, 2, 2, 3, 3, 4, 4]

C = []
costs = []

def findMin(S, R):
    minCost = 99999.0
    minElement = -1
    for i, s in enumerate(S):
        try:
            cost = w[i]/(len(s.intersection(R)))
            if cost < minCost:
                minCost = cost …