在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中做約束滿足

回答

相關問題