找到三個整數，其總和最接近給定數量N

閱讀Finding three elements in an array whose sum is closest to a given number後，這是我嘗試在執行這樣的算法找到三個整數，其總和最接近給定數量N

def findThree(seq, goal): 

    # initialize the differences 
    goalDifference = float("inf") 
    dl = -1 
    dr = -1 
    dx = -1 

    for x in range(len(seq)-1): 

     left = x+1 
     right = len(seq)-1 


     while (left < right): 

      # if the absolute value of the previous set and the goal is less than the current goalDifference, 
      # keep track of the new set 
      if(abs(goal - (seq[left] + seq[right] + seq[x])) < goalDifference): 
       dl = left 
       dr = right 
       dx = x 

      tmp = seq[left] + seq[right] + seq[x] 

      if tmp > goal: 
       right -= 1 
      elif tmp < goal: 
       left += 1 
      else: 
       return [seq[left],seq[right],seq[x]] 

    # if no match is found, return the closest set 
    return [seq[dl],seq[dr], seq[dx]]

該算法非常適合尋找確切的解決方案，給出

arr = [89, 120, 140, 179, 199, 259, 259, 259, 320, 320] 

findThree(arr, 349) // want to get [120, 140, 89] 
>> [120, 140 89] // success 

findThree(arr, 439) // want to get [140, 179, 120] 
>> [140, 179,120] // success

然而，當我想看看它是否會返回最近的地方，它返回

findThree(arr, 350) // only 1 more than 349, should return [120, 140, 89] 
>> [320, 320, 259] // fail 

findThree(arr, 440) // only 1 more than 439, should return [140, 179, 120] 
>> [320, 320, 259] // fail

看來，當我想要它返回「cloest」元素時，它總是返回[320,320,259]。我一直在看代碼幾個小時，但仍然無法弄清楚什麼是錯的。

來源

2014-09-21 user3277633

我很快瀏覽了你的代碼，主要問題是「目標差異」從未改變過。

你需要擠出「淨勝球」，否則所有組合都在「淨勝球」之內，顯然你最終會得到最後一組作爲答案。

來源

2014-09-21 19:52:43

嗯我不太確定我得到你的建議。在參數中，目標是我希望儘可能接近的最終總和 – user3277633 2014-09-21 19:53:54

啊，我明白了，謝謝！ – user3277633 2014-09-21 20:01:22

太棒了，盡情享受吧！ – 2014-09-21 20:03:06

你可以這樣做：

def find3(tgt, arr): 
    lowest=[float('inf')] 
    for i in range(0,len(arr)-2): 
     j=i+1 
     k=len(arr)-1 
     while k>=j: 
      t=tuple(arr[x] for x in (i, j, k)) 
      sum_t=sum(t) 
      if sum_t==tgt: 
       return t 
      elif sum_t<sum(lowest): 
       lowest=t  
      if sum_t>0: 
       k-=1 
      else: 
       j+=1      

    return lowest

這對於您所描述的所有情況都適用。

來源

2014-09-21 20:33:20 dawg

其實，這裏的問題是，你沒有跟蹤最接近的數字組合。根據當前算法，您的代碼將檢查組合，直到left = right-1 和x=left-1 (since left = x+1);。在執行循環結束時，如果沒有達到正確的組合，您將始終有x=259,left=320和right=320。這就是爲什麼當調用findThree(arr, 350)和findThree(arr, 440)時，它返回最後一次迭代的值總是[320, 320, 259]。的溶液可以採取三個可變close1close2和close3和for循環開始前他們初始化爲0，並在for循環添加if語句後以下：

if(abs(goal - (seq[left] + seq[right] + seq[x])) < abs(goal - (close1 + close2 + close3))): 
close1 = seq[left] 
close2 = seq[right] 
close3 = seq[x]

上述聲明將檢查從最接近前一組和當前一組left，right和陣列的x元件，並且改變close1，close2close2和當前設置左，右和x的，如果目前的組合比的left，right和以前的記錄更近，分別保存在close1,close2和close3中。其他close1,close2和close3不得更改。並在代碼結尾

#if no match is found,return the closest set 
return [close1 ,close2, close3]

來源

2014-09-21 20:41:37 Akhil

找到三個整數，其總和最接近給定數量N

回答

相關問題