如何从所有蛮力组合中找到最佳解决方案？

Question

我想从字典的所有暴力组合中找到最佳解决方案。对于问题的上下文，我需要找出在给定重量限制的情况下运输所有奶牛所需的最少行程次数。

这些组合已经通过辅助函数 get_partitions 提供给我了。函数 returns 一个嵌套列表，每个内部列表代表一次旅行和该旅行中奶牛的名字。

辅助函数：

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']]

如果有人能帮我指出我哪里做错了，那将不胜感激。

编辑：添加了辅助函数

Answer 1

我们可以将其视为深度优先搜索问题。

def getCows(dict, limit):
    best_solution = []
    best_solution_score = 0

    def dfs(current_cows, current_total):
        nonlocal best_solution_score
        nonlocal best_solution
        if current_total > best_solution_score:
            #replace best solution
            best_solution = [tuple(sorted(current_cows))]
            best_solution_score = current_total
        elif current_total == best_solution_score:
            #add to best solution
            best_solution.append(tuple(sorted(current_cows))) 
        for cow, weight in dict.items():
            if cow not in current_cows and current_total + weight <= limit:
                #if adding next cow under limit recurse
                dfs(current_cows + [cow], current_total + weight)

    dfs([], 0)
    return list(set(best_solution)) #remove duplicates

cows = {'MooMoo': 50, 'Miss Bella': 25, 'Boo': 20,
    'Milkshake': 40, 'Horns': 25, 'Lotus': 40}


print(getCows(cows, limit=100))
>>>[('Horns', 'Miss Bella', 'MooMoo'), ('Boo', 'Lotus', 'Milkshake')]

如何从所有蛮力组合中找到最佳解决方案？

How to find best solution from all brute force combinations?

algorithm

knapsack-problem

brute-force

python-3.x