找到大于指定值的整数组合的算法

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) 

既然我们知道解决方案存在，我们希望重新创建解决方案。我们在这里使用回溯技术。你也可以在互联网上很容易地找到很多有关这方面的优秀教程。