为什么这个蛮力算法产生不正确的结果？

问题描述：

我想写一个蛮力算法，尽量减少一群奶牛的旅程，受条件在文档字符串。为什么这个蛮力算法产生不正确的结果？

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行。我一遍又一遍地检查代码，并返回一个次优的答案：

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

语法罚款;没有错误产生，但我有一个次优（但有效）的答案。为什么是这样？

我有一种感觉，'分钟（valid_trips）'是不是做你想让它是什么。 [看到这个问题。]（https://stackoverflow.com/questions/13052857/comparing-two-lists-using-the-greater-than-or-less-than-operator） –

@JaredGoguen我试图得到具有最少元素的'valid_trips'的子列表。 – alexqwx

答

这里的问题是：

如何找到一个嵌套列表最短的子表？

要做到这一点，改变最后一行：

min(valid_trips, key=len)

为什么这个蛮力算法产生不正确的结果？

相关推荐