爲什麼這個蠻力算法產生不正確的結果？

我想寫一個蠻力算法，儘量減少一羣奶牛的旅程，受條件在文檔字符串。爲什麼這個蠻力算法產生不正確的結果？

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

語法罰款;沒有錯誤產生，但我有一個次優（但有效）的答案。爲什麼是這樣？

來源

2017-06-03 alexqwx

我有一種感覺，'分鐘（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)

來源

2017-06-03 15:08:01

爲什麼這個蠻力算法產生不正確的結果？

回答

相關問題