为什么这种蛮力算法会产生错误的结果？

Question

我正在尝试编写一个蛮力算法，根据文档字符串中的条件，最大限度地减少一群奶牛的行程次数。

def brute_force_cow_transport(cows,limit=10):
    """
    Finds the allocation of cows that minimizes the number of spaceship trips
    via brute force.  The brute force algorithm should follow the following method:

    1. Enumerate all possible ways that the cows can be divided into separate trips
    2. Select the allocation that minimizes the number of trips without making any trip
        that does not obey the weight limitation

    Does not mutate the given dictionary of cows.

    Parameters:
    cows - a dictionary of name (string), weight (int) pairs
    limit - weight limit of the spaceship (an int)

    Returns:
    A list of lists, with each inner list containing the names of cows
    transported on a particular trip and the overall list containing all the
    trips
    """
    def weight(sub):
        sum = 0
        for e in sub:
            sum += cows[e]
        return sum

    valid_trips = []
    for part in list(get_partitions(cows)):
        if all(weight(sub) <= limit for sub in part):
            valid_trips.append(part)
    return min(valid_trips)

(题目中已经给出函数get_partitions和字典cows)

我哪里做错了？我已经检查了权重函数（评估给定宇宙飞船旅行的重量），因此它必须在最后 5 行中。我一遍又一遍地检查代码，returns 一个次优答案：

[['Florence', 'Lola'],
 ['Maggie', 'Milkshake', 'Moo Moo'],
 ['Herman'],
 ['Oreo'],
 ['Millie'],
 ['Henrietta'],
 ['Betsy']]

语法没问题；没有产生任何错误，但我有一个次优（但有效）的答案。这是为什么？

Answer 1

这里的问题是：

How do I find the shortest sublist in a nested list?

为此，将最后一行更改为：

min(valid_trips, key=len)

为什么这种蛮力算法会产生错误的结果？

Why is this brute force algorithm producing the incorrect result?

python

brute-force