python - 给定组成本和元素成本的精确覆盖问题

Question

如果每个组和每个元素都有自己的成本，如何解决集合覆盖问题。

我为此想出了一个贪心算法，但它并非在所有情况下都有效。需要一个准确的算法。

这就是我能找到的关于这个主题的全部内容：

这个和这个

但是考虑到组的成本以及每个元素的成本，该算法不起作用。

请告诉我我可以用什么来解决这个问题。

from queue import PriorityQueue

N = int(input())
dct = {}
groups = PriorityQueue()

for i in range(N):
    a,c = [int(j) for j in input().split()]
    dct[a] = c 

M = int(input())


for i in range(M): 
    k,c = [int(j) for j in input().split()]
    s = 0
    tmp = []
    for j in input().split():
        j_=int(j)
        if j_ in dct:
            s+=dct[j_]
            tmp.append(j_)
    d = c-s
    if d<0:
        groups.put([d, c, tmp])  

s = 0
while not groups.empty():
    #print(dct)
    #for i in groups.queue:
    #    print(i)
    g = groups.get()
    if g[0]>0:
        break
    #print('G',g)
    #print('-------')
    for i in g[2]:
        if i in dct:
            del(dct[i])
    s += g[1]
    groups_ = PriorityQueue()
    for i in range(len(groups.queue)):
            g_ = groups.get()
            s_ = 0
            tmp_ = []
            for i in g_[2]:
                if i in dct:
                    s_+=dct[i]
                    tmp_.append(i)
            d = g_[1]-s_
            groups_.put([d, g_[1], tmp_])
    groups = groups_ 

for i in dct:
    s+=dct[i]

print(s)

标签： pythonalgorithm