找到三个整数，其总和最接近给定数量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

回答

相关问题