計算最接近的總和，以X使用號碼列表

我有號碼列表計算最接近的總和，以X使用號碼列表

[850, 1300, 810, 590, 590, 910, 480, 1170, 430, 530, 295, 970, 560, 410, 570, 680, 180, 180, 400, 1040]

我想給函數的整數參數，並把它通過在列表中合計數值返回最接近的數量可能，並告訴我用它來達到這個目標的數字。

例如，我給它數3255，它會吐出像

1300, 810, & 1170 sum to 3280

（我不知道這是否是從這個例子中，最接近實際相結合，只顯示它應該如何工作）

來源

2014-11-05 user2936448

歡迎使用堆棧溢出！看起來你希望我們爲你寫一些代碼。儘管許多用戶願意爲遇險的編碼人員編寫代碼，但他們通常只在海報已嘗試自行解決問題時才提供幫助。證明這一努力的一個好方法是包含迄今爲止編寫的代碼，示例輸入（如果有的話），期望的輸出和實際獲得的輸出（控制檯輸出，堆棧跟蹤，編譯器錯誤 - 無論是適用）。您提供的細節越多，您可能會收到的答案就越多。 – 2014-11-05 16:14:38

查看'itertools'，特別是'itertools.combinations'。 – 2014-11-05 16:19:46

看起來這個問題與[揹包問題]（https://en.wikipedia.org/wiki/Knapsack_problem）類似，這很難有效解決。維基百科文章列舉了幾種解決方法，包括一些僞代碼。 – 9000 2014-11-05 16:19:59

如果你只是想暴力破解的問題，使用修改冪配方從itertools：

import itertools as it 

def powerset(iterable): 
    "powerset([1,2,3]) --> (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" 
    s = list(iterable) 
    return it.chain.from_iterable(it.combinations(s, r) for r in range(1, len(s)+1)) 

def f(n, lst): 
    return min((abs(n-sum(i)), i) for i in powerset(lst))[1]

這種方法不適用於initi工作儘管因爲powersets呈指數級增長，所以列表比例子列表大得多。

來源

2014-11-05 16:50:31

以下是執行更好的複雜性比蠻力

假設輸入陣列ARR []，有一個堆棧來存儲輸出

recurse(n, index) 
{ 
    int temp = n; int ind = index; 
    while(ind<arr.length) 
     if(arr[ind]>n) 
      ind++; 
     else 
      temp = temp - arr[ind]; 
      stack.push(temp); 
      if(temp==0) 
       return true; 
      result = recurse(temp,ind+1); 
      if(result is false) 
       temp = n; stack.pop(); 
       ind++; 
      else 
       break; 
    if(ind==arr.length) then return false 
} 
print stack

實施例的僞代碼：如果陣列是以下和你需要找到26 然後它執行如下

遞歸（26,0） 26-11 - > recurse（15,1）自26-11 = 15;推動11堆棧遞歸（15,1） 15-9 - >遞歸（6,2）自15-9 = 6;將堆棧中的9推回遞歸（6,2） 6-5 - >遞歸（1,4）將堆棧中的5推入因爲沒有小於1的元素，所以遞歸（1,4）返回false從堆棧中彈出5自從除了5之外沒有小於6的元素，從堆棧中彈出9個現在它計算15-8 = 7遞歸（7,3），按下8堆棧遞歸（7,3）按下7堆棧返回true

最後打印堆棧11,8,7其中11 + 8 + 7 = 26

來源

2014-11-06 07:58:13 Ashok

計算最接近的總和，以X使用號碼列表

回答

相關問題