python - 给定所需元素列表，如何从列表中选择最佳(成本)卖家团队

Question

鉴于需要的项目列表，我需要选择一个供应商团队，以便每个项目都有一个供应商(没有遗漏的项目)并且所有项目的总成本尽可能低。例如

vendors = [target, kmart, bunnings, walmart]
items_needed = ['rope', 'tape', 'staples', 'cardboard', 'paper']

target = (['rope', 'tape'], 200)
kmart = (['rope', 'staples', 'paper'], 1000)
bunnings = (['cardboard'], 500) 
walmart = (['rope', 'paper', 'scissors'], 240)

我可以使用贪心法选择供应商团队，但我不知道您将如何获得最佳的整体团队。

因为它会根据哪个选项以每件商品的最低成本提供最多的商品来选择每个结果，然后将其添加到列表中。

我需要它根据每件元素的成本选择最佳的整体团队，并提供每件元素。

所以结果应该是:[target, kmart, bunnings]

因为它拥有每件商品的总体成本最低。

感谢您的帮助。

Answer 1

会有更好的方法，如果我找到它，我会更新，但要获取至少包含所需元素的商店列表:

vendor_items = [v[0] for v in vendors]

# see link below
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


[
    list(powerset(vendors))[index]
    for index, l in enumerate(powerset(vendor_items))
    if set().union(*l) >= set(items_needed) # see link below
]

# returns list of possible stores that together cover items needed
# [((['rope', 'tape'], 200), (['rope', 'staples', 'paper'], 1000), (['cardboard'], 500)),
#  ((['rope', 'tape'], 200), (['rope', 'staples', 'paper'], 1000), (['cardboard'], 500), (['rope', 'paper', 'scissors'], 240))]

How to merge sets

Powerset method from itertools recipes

powerset 是矫枉过正:对于 powerset([1,2,3]) 如果 (1,2) 工作我们不需要 (1,2,3)，如果可以的话，您真的不想调用 list(powerset(vendor_items))