给定所需的物品清单,我需要选择一个供应商团队,以便每个物品都有一个供应商(没有丢失的物品),并且所有物品的总成本是最低的。例如

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/

10-12 16:37