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

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

例如，如果我有数组[1,4,5,10,17,34]，并且我指定了最小和为31，那么函数将返回[1,4,10,17]。 或者，如果我想将它限制为最大数组大小为2，那么它会返回[34]。

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

---

像这样？ 它返回值，但可以很容易地调整以返回序列。

算法：假设排序后的输入，测试大于min的最小和的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

---

这更像是一个混合解决方案，具有动态编程和后台追踪功能。 我们可以单独使用反向跟踪来解决这个问题，但是我们必须做详尽的搜索（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)

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

链接地址: http://www.djcxy.com/p/73973.html

上一篇: Algorithm for finding a combination of integers greater than a specified value

下一篇: Using $1, $2, etc. global variables inside method definition