给定所需的物品清单,我需要选择一个供应商团队,以便每个物品都有一个供应商(没有丢失的物品),并且所有物品的总成本是最低的。例如
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)
我可以使用贪婪的方法选择一个供应商团队,但我不知道您将如何获得最佳的整体团队。
因为它基于哪个选项提供的项目最多,每个项目的成本最低,来选择每个结果,然后将其添加到列表中。
我需要它根据每件物品的成本来选择最佳的整体团队,并提供每件需要的物品。
所以结果应该是:[目标,kmart,邦宁]
因为那总的来说是最便宜的所有物品。
谢谢你的帮助。
最佳答案
会有更好的方法,如果找到,我会进行更新,但要获取至少涵盖所需物品的商店列表:
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))
关于python - 给定所需物品 list ,如何从 list 中选择最佳的(成本)卖方团队,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/56075301/