我想从字典的所有蛮力组合中找到最佳解决方案 . 对于问题的背景,我需要找出在给定重量限制的情况下运输所有奶牛所需的最小行程数 .
已经通过辅助函数 get_partitions
给了我这些组合 . 该函数返回一个嵌套列表,每个内部列表代表一次旅行以及该行程中的奶牛名称 .
助手功能:
def partitions(set_):
if not set_:
yield []
return
for i in range(2**len(set_)//2):
parts = [set(), set()]
for item in set_:
parts[i&1].add(item)
i >>= 1
for b in partitions(parts[1]):
yield [parts[0]]+b
def get_partitions(set_):
for partition in partitions(set_):
yield [list(elt) for elt in partition]
我试图做的是按长度排序所有组合,然后用嵌套循环迭代它们 . 如果总重量超过限制,那么我会突破内循环并将下一个子列表附加到另一个列表 . 问题是下一个子列表仍然包含来自分区的剩余列表,因为它们的总权重低于限制 .
我的代码:
def brute_force_cow_transport(cows, limit):
# Generate and sort all combinations by length
partitions = [item for item in get_partitions(cows)]
partitions.sort(key=len)
# Iterate over each sublist of combinations
possibles = []
for partition in partitions:
trips = []
for section in partition:
total = sum([cows.get(cow) for cow in section])
if total > limit:
break
else:
# Appending next sublists create duplicates
trips.append(section)
possibles.append(trips)
# Remove duplicates from possible solutions
best = []
for item in possibles:
if item and item not in best:
best.append(item)
return min(best)
当我运行我的函数时,它每次都会返回不同的结果 . 我认为这是因为我在结果中附加的剩余子列表导致了问题,但我不确定:
cows = {'MooMoo': 50, 'Miss Bella': 25, 'Boo': 20,
'Milkshake': 40, 'Horns': 25, 'Lotus': 40}
>>> brute_force_cow_transport(cows, limit=100)
[['Boo', 'Miss Bella', 'MooMoo']]
正确的结果:
[['MooMoo', 'Horns', 'Miss Bella'], ['Milkshake', 'Lotus', 'Boo']]
如果有人能帮助我指出我哪里出错了,那将非常感激 .
编辑:添加了辅助函数
1 回答
我们可以将其作为深度优先搜索问题来处理 .