子集和算法和遞歸

經過一番研究，下面是我在SO上發現的subset_sum遞歸的修改版本。修改後的版本不僅會返回確切的總和（如果有的話），還會返回最接近的整數集合（如果找不到精確的總和）。此外，是確定必須有多少數字加起來，以確定最終總和子集和算法和遞歸

def findFourPlus(itemCount, seq, goal): 
    goalDifference = float("inf") 
    closestPartial = [] 
    subset_sum(itemCount, seq, goal, goalDifference, closestPartial, partial=[]) 
    print(closestPartial) 

def subset_sum(itemCount, seq, goal, goalDifference, closestPartial, partial): 
s = sum(partial) 

# check if the partial sum is equals to target 
if(len(partial) == itemCount): 
    if s == goal: 
      print(partial) 
    else: 
     if(abs(goal - s) < goalDifference): 
      goalDifference = abs(goal - s) 
      closestPartial = partial   

for i in range(len(seq)): 
    n = seq[i] 
    remaining = seq[i+1:] 
    subset_sum(itemCount, remaining, goal, goalDifference, closestPartial, partial + [n])

列表尺寸要求

我面對現在的問題是，closesetPartial將永遠是一個空列表，因爲每個電話subset_sum（）將刷新cloestPartial回到一個空的列表。我試圖移動goalDifference和cloestPartial初始化subset_sum函數之外，但我返回與本地變量'goalDifference'之前引用分配錯誤。

我能做些什麼來既保留遞歸算法，同時保持迄今爲止的最接近總和？有沒有更好的方法來解決這個問題？

來源

2014-09-21 user3277633

初始化closestPartial和goalDifference在調用subset_sum之外並將它們作爲參數傳遞。要麼保留一個參考每個subset_sum呼叫傳遞的單個closestPartial，要麼將closestPartial的副本傳遞給每個subset_sum調用 - 前者可能效率更高，而後者更容易實現/推理，因爲它將會沒有副作用。

來源

2014-09-21 22:30:07

嗨，謝謝你的建議。我已經編輯了上面的算法，但現在它返回「TypeError：subset_sum（）缺少2個必需的位置參數：'closestPartial'和'partial'」，我不明白，因爲我已經定義了nearestPartial，partial是默認參數 – user3277633 2014-09-21 23:45:19

只是開玩笑，似乎我忘記了底部subset_sum遞歸調用。上述算法仍然只返回一個空的最接近的部分列表。任何想法爲什麼？ – user3277633 2014-09-21 23:47:12

@ user3277633我認爲發生了什麼是你正在改變'nearestPartial'引用來指向'partial'引用，但外層函數沒有看到這個 - 它仍然引用了原來的'nearestPartial'，而不是到更新的參考。您可以將'partial'元素複製到'closestPartial'中，否則您可以將'nearestPartial'包裝並繞過包裝，例如'struct Wrapper {closestPartial []}' - 然後當你更新包裝器中的引用時，外部函數將會看到更新的引用。 – 2014-09-21 23:55:36

子集和算法和遞歸

回答

相關問題