在Python中做约束满足

假设我有多个用户，其中每个用户都有一组介于0和n之间的数字。例如，一个用户可能有一组{3, 7}，另外可能有{7, 8, 9}等在Python中做约束满足

我想获得用户数最少的，如果我把所有的集的工会，我会得到一套所有数字在0和n之间。

奖励积分如果您想出一种方法，也可以让我为每个用户分配一个可变价格（而不是像上面那样使用1），这样算法就可以找到总用户数最少的用户组合。

我已经看到在Python中处理约束满足的包（like this one），但我不知道如何使用它们。如果他们可以用于这个，很好。

2014-08-31 Ram Rachum

看起来像一个难题。我认为暴力是不可能的？ – 2014-08-31 15:32:33

http://en.wikipedia.org/wiki/Set_cover_problem – 2014-08-31 16:03:46

它确实设置了封面，因此可能没有多项式时间解决方案。您可以使用指数动态程序或将该问题表述为[ILP]（http://en.wikipedia.org/wiki/Integer_programming），并使用通用解算器。 – 2014-08-31 21:18:17

以下是PuLP/GLPK的解决方案。我以前从来没有使用过PuLP，但是它在PyPI上，似乎能完成这项工作。 GLPK非常好，免费。

from collections import defaultdict, namedtuple 
from pulp import * 


User = namedtuple('User', ('coverage', 'price')) 


def solvesetcover(users): 
    vars = [LpVariable('x{}'.format(i), 0, 1, cat='Binary') for i, user in enumerate(users)] 
    prob = LpProblem() 
    totals = defaultdict(int) 
    for user, var in zip(users, vars): 
     prob += user.price * var 
     for elt in user.coverage: 
      totals[elt] += var 
    for total in totals.values(): 
     prob += total >= 1 
    GLPK(msg=0).solve(prob) 
    return [user for user, var in zip(users, vars) if value(var)] 


if __name__ == '__main__': 
    users = [] 
    users.append(User({1, 2, 3, 4, 5, 6, 7}, 1.16)) 
    users.append(User({8, 9, 10, 11, 12, 13, 14}, 1.08)) 
    users.append(User({1, 8}, 1.04)) 
    users.append(User({2, 3, 9, 10}, 1.02)) 
    users.append(User({4, 5, 6, 7, 11, 12, 13, 14}, 1.01)) 
    print(solvesetcover(users))

来源

2014-09-01 18:58:04

在Python中做约束满足

回答

相关问题