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

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