找到大於指定值的整數組合的算法

Question

我一直在試圖開發一種算法，它將採用輸入數組並返回一個數組，使得包含在其中的整數是總和最小的整數的組合超過規定值（限於組合尺寸k）。例如，如果我有數組[1,4,5,10,17,34]，並且我指定了最小和爲31，則該函數將返回[1,4,10,17]。或者，如果我想將它限制爲最大數組大小爲2，那麼它會返回[34]。

有沒有高效方法做到這一點？任何幫助，將不勝感激！

Answer 1

這樣的事情？它返回值，但可以很容易地調整以返回序列。

算法：假定排序輸入，測試比分鐘的最小總和的k長度的組合，第一個數組元素大於MIN後停止。

JavaScript的：

var roses = [1,4,5,10,17,34] 

function f(index,current,k,best,min,K) 
{ 
    if (roses.length == index) 
     return best 
    for (var i = index; i < roses.length; i++) 
    { 
     var candidate = current + roses[i] 
     if (candidate == min + 1) 
      return candidate 
     if (candidate > min) 
      best = best < 0 ? candidate : Math.min(best,candidate) 
     if (roses[i] > min) 
      break 
     if (k + 1 < K) 
     { 
      var nextCandidate = f(i + 1,candidate,k + 1,best,min,K) 
      if (nextCandidate > min) 
       best = best < 0 ? nextCandidate : Math.min(best,nextCandidate) 
      if (best == min + 1) 
       return best 
     } 
    } 
    return best 
} 

輸出：

console.log(f(0,0,0,-1,31,3)) 
32 

console.log(f(0,0,0,-1,31,2)) 
34 

Answer 2

這更是一個混合溶液中，用動態規劃和回溯。我們可以單獨使用反向跟蹤來解決這個問題，但是我們必須做詳盡的搜索（2^N）才能找到解決方案。 DP部分優化後臺追蹤中的搜索空間。

import sys 
from collections import OrderedDict 
MinimumSum = 31 
MaxArraySize = 4 
InputData = sorted([1,4,5,10,17,34]) 
# Input part is over  

Target  = MinimumSum + 1 
Previous, Current = OrderedDict({0:0}), OrderedDict({0:0}) 
for Number in InputData: 
    for CurrentNumber, Count in Previous.items(): 
     if Number + CurrentNumber in Current: 
      Current[Number + CurrentNumber] = min(Current[Number + CurrentNumber], Count + 1) 
     else: 
      Current[Number + CurrentNumber] = Count + 1 
    Previous = Current.copy() 

FoundSolution = False 
for Number, Count in Previous.items(): 
    if (Number >= Target and Count < MaxArraySize): 
     MaxArraySize = Count 
     Target  = Number 
     FoundSolution = True 
     break 

if not FoundSolution: 
    print "Not possible" 
    sys.exit(0) 
else: 
    print Target, MaxArraySize 

FoundSolution = False 
Solution  = [] 

def Backtrack(CurrentIndex, Sum, MaxArraySizeUsed): 
    global FoundSolution 
    if (MaxArraySizeUsed <= MaxArraySize and Sum == Target): 
     FoundSolution = True 
     return 
    if (CurrentIndex == len(InputData) or MaxArraySizeUsed > MaxArraySize or Sum > Target): 
     return 
    for i in range(CurrentIndex, len(InputData)): 
     Backtrack(i + 1, Sum, MaxArraySizeUsed) 
     if (FoundSolution): return 
     Backtrack(i + 1, Sum + InputData[i], MaxArraySizeUsed + 1) 
     if (FoundSolution): 
      Solution.append(InputData[i]) 
      return 

Backtrack(0, 0, 0) 
print sorted(Solution) 

注：按在的問題，最小總和和最大數組大小由你給出的實施例是嚴格大於分別指定，值較大和較小。

對於此輸入

MinimumSum = 31 
MaxArraySize = 4 
InputData = sorted([1,4,5,10,17,34]) 

輸出是

[5, 10, 17] 

其中爲，爲了本輸入

MinimumSum = 31 
MaxArraySize = 3 
InputData = sorted([1,4,5,10,17,34]) 

輸出是

[34] 

說明

Target  = MinimumSum + 1 
Previous, Current = OrderedDict({0:0}), OrderedDict({0:0}) 
for Number in InputData: 
    for CurrentNumber, Count in Previous.items(): 
     if Number + CurrentNumber in Current: 
      Current[Number + CurrentNumber] = min(Current[Number + CurrentNumber], Count + 1) 
     else: 
      Current[Number + CurrentNumber] = Count + 1 
    Previous = Current.copy() 

程序的這一部分發現從輸入數據，以使數之和爲1至最大可能數目所需數量的最小數目（這是所有的總和輸入數據）。它是一種動態編程解決方案，爲揹包問題。你可以在互聯網上閱讀。

FoundSolution = False 
for Number, Count in Previous.items(): 
    if (Number >= Target and Count < MaxArraySize): 
     MaxArraySize = Count 
     Target  = Number 
     FoundSolution = True 
     break 

if not FoundSolution: 
    print "Not possible" 
    sys.exit(0) 
else: 
    print Target, MaxArraySize 

程序的這一部分，認定其匹配MaxArraySize標準Target值。

def Backtrack(CurrentIndex, Sum, MaxArraySizeUsed): 
    global FoundSolution 
    if (MaxArraySizeUsed <= MaxArraySize and Sum == Target): 
     FoundSolution = True 
     return 
    if (CurrentIndex == len(InputData) or MaxArraySizeUsed > MaxArraySize or Sum > Target): 
     return 
    for i in range(CurrentIndex, len(InputData)): 
     Backtrack(i + 1, Sum, MaxArraySizeUsed) 
     if (FoundSolution): return 
     Backtrack(i + 1, Sum + InputData[i], MaxArraySizeUsed + 1) 
     if (FoundSolution): 
      Solution.append(InputData[i]) 
      return 

Backtrack(0, 0, 0) 

既然我們知道解決方案存在，我們希望重新創建解決方案。我們在這裏使用回溯技術。你也可以在互聯網上很容易地找到很多有關這方面的優秀教程。