找到在Python中求和給定值的子數組

Question

如果給出一個子數組[1,2,3,4]和一個數值8.我想返回子數組[1,3,4]。我在我的代碼中有一個錯誤，我不確定如何修復它，因爲我是遞歸的新手。下面我有我的Python代碼。我正在找回[3,4]的值來顯示這顯然不是正確的答案。我如何獲得數組中的第一個元素？

def main(): 
    s = 0 
    a = [1,2,3,4] # given array 
    sa = [] # sub-array 
    w = 8 # given weight 
    d = False 
    d, sa = checkForWeight(a,w,s,d,sa) 
    print sa 

def checkForWeight(a,w,s,d,sa): 
    l = len(a) 
    s += a[0] 
    sa.append(a[0]) 
    if s == w: 
     d = True 
     return d, sa 
    else: 
     try: 
      d, sa = checkForWeight(a[1:],w,s,d,sa) 
      if d != True: 
       d, sa = checkForWeight(a[2:],w,s,d,sa) 
      else: 
       return d, sa 
     except: 
      sa = [] # i put this here because I want to erase the incorrect array 
    return d, sa 

Answer 1

我做了一個可行的遞歸解決方案，希望它有助於：

def main(): 
    success, solution = WeightChecker((1,2,3,4)).check(8) 
    print solution 

class WeightChecker(object): 
    def __init__(self, to_check): 
     self._to_check = to_check 
    def check(self, weight): 
     return self._check((), 0, weight) 
    def _check(self, current_solution, index_to_check, remaining_weight): 
     if remaining_weight == 0: 
      return True, current_solution 
     if index_to_check == len(self._to_check): 
      return False,() 
     current_check = self._to_check[index_to_check] 
     success, solution = self._check(current_solution + (current_check,), index_to_check + 1, remaining_weight - current_check) 
     if not success: 
      success, solution = self._check(current_solution, index_to_check + 1, remaining_weight) 
     return success, solution 

（動態規劃方法是keredson建議更好）

Answer 2

你需要你的總和匹配任何子陣？或全部子排列？ （或者最短或最長？）正確的答案將高度依賴於此。

順便說一句，這是揹包問題的一個變體光盤：https://en.wikipedia.org/wiki/Knapsack_problem

而且，你的遞歸策略似乎是在複雜性因子。 （如果是代碼測試，這可能會使申請人失敗。）我強烈建議採用動態編程方法。

編輯

如果你需要的所有可能的，你正在尋找一個NP問題。我建議專注於易於實施/維護，而不是絕對的表現來展示你的技能。例如：

import itertools 

def find_all_subsets_that_sum(elements, total): 
    for i in range(len(elements)): 
    for possible in itertools.combinations(elements, i+1): 
     if sum(possible)==total: 
     yield possible 

print list(find_all_subsets_that_sum([1,2,3,4,5,6,7,8,9,10], 10)) 

是不是絕對的最快的（你可以做一個自我滾遞歸解決了很多的修剪），但它會是一樣大O是什麼更復雜的解決方案，你上來用。 （所有的解決方案將通過O爲主（正選N/2）。）很少有面試的考生將一些模棱兩可的話：

This is not as fast as it can be, but it's within spitting distance of the fastest, and would likely be the best ROI on developer hours, in both implementation and maintenance. Unless of course the data set we're parsing is huge, in which case i would recommend relaxing the requirements to returning a heuristic of some number of solutions that could be calculated with a O(n^2) dynamic programming solution."

而且你可以用它來脫穎而出。

Answer 3

直接的問題是你在函數的頂部追加了一個[0]給sa，但後來使用子調用的返回值來銷燬它。爲了修補這個，添加一個條款，你返回最終結果之前：

except: 
     sa = [] # i put this here because I want to erase the incorrect array 
if d: 
    sa = [a[0]] + sa 
print "Leave: drop", d,sa 
return d, sa 

我建議您按照建議的意見：而不是通過周圍這麼多的東西，專注於部分解決方案的局部控制。

嘗試一種解決方案的兩種方法：有和沒有當前元素。你的遞歸調用看起來像這樣：

sa = checkForWeight(a[1:], w)   # Solutions without first element 
    -- and -- 
sa = checkForWeight(a[1:], w-a[0]) # Solutions using first element 

You don't have to return a success flag; if **sa** is None or empty, the call failed to find a solution. If it succeeded, in the **w-a[0]** call, then you also need to prepend each solution in **sa** with **a[0]**. 

這是否讓你感動？