arrays - 查找大于指定值的整数组合的算法

Question

我一直在尝试开发一种算法，该算法将采用输入数组并返回一个数组，使得其中包含的整数是最小和大于指定值的整数组合（仅限于大小k的组合）。

例如，如果我有数组 [1,4,5,10,17,34] 并且我指定的最小和为 31，则该函数将返回 [1,4,10,17]。或者，如果我希望它限制为最大数组大小为 2，它只会返回 [34]。

有没有一种有效的方法来做到这一点？任何帮助，将不胜感激！

Answer 1

像这样的东西？它返回值，但可以很容易地适应返回序列。

算法：假设输入已排序，测试 k 长度组合是否最小和大于 min，在第一个大于 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

这更像是一种混合解决方案，具有动态规划和回溯。我们可以单独使用 Back Tracking 来解决这个问题，但是我们必须进行穷举搜索 (2^N) 才能找到解决方案。DP部分优化了Back Tracking中的搜索空间。

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

程序的这一部分，查找与标准Target匹配的值MaxArraySize。

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)

现在我们知道解决方案存在，我们想要重新创建解决方案。我们在这里使用回溯技术。您也可以在互联网上轻松找到很多关于此的优秀教程。