在Python中进行约束满足

Question

假设我有一些用户，每个用户都有一组数字，这些数字的范围是从 0 到 n。比如，一个用户可能有一组数字 {3, 7}，另一个用户可能有 {7, 8, 9}，等等。

我想找出最少的用户数量，这些用户的数字组合在一起后，能覆盖从 0 到 n 的所有数字。

如果你能想出一种方法，让我给每个用户设置不同的价格（而不是像上面那样统一用 1），这样算法就能找到总价格最低的用户组合，那就更好了。

我见过一些处理约束满足问题的Python库（比如这个），但我不知道怎么用。如果这些库可以用来解决这个问题，那就太好了。

Answer 1

这里有一个关于 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))