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

Question

我一直在尝试开发一种算法，该算法将接受一个输入数组并返回一个数组，使得其中包含的整数是整数的组合，最小总和大于指定值(限制为大小的组合 < em>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