仅使用Y数的所有可能性小于X？

Question

说我有这些数字:[2,25,37,54,54,76,88,91,99](这些是随机的)

我需要找到小于100的那些数字的所有组合.并非所有数字都必须在这些组合中使用.例子:2,2 + 25 + 37,54 + 25

我怎样才能在JavaScript中实现这一目标？

谢谢

Answer 1

这是子集和问题的修改版本.获取功率集是一种强力解决方案,虽然简单,但对于大型列表来说效率低,需要O(2 ^ N)时间.子集和是NP完全的,所以你不能在低于指数的时间内解决它,但如果你分而治之,你可以在一般情况下更快地解决它(但不是最坏的情况)¹.你做的是,将数组分成两半并在每一半上运行powerset函数(来自Adam的答案),除了你用数组保存数组的总和(实际上,保存数组的总和会产生巨大的性能)即使你不拆分数组也会提升,因为它可以消除大量的冗余添加):

var sum = ps[j].sum + arr[i] //huge optimization! don't redo all the addition
if (sum < 100) { //don't include this check if negative numbers are allowed
    arrCandidate.sum = sum;
    ps.push(arrCandidate);
}

然后,您按总和对每一半的功率进行排序,按相反方向排序

ps1.sort(function(b,a){return a.sum-b.sum;});
ps2.sort(function(a,b){return a.sum-b.sum;});

现在,您可以浏览两个列表并返回总和小于100的数组的每个组合:

var pos1 = 0;
var pos2 = -1;
while (pos1 < ps1.length) {
    var arr1 = ps1[pos1];
    while (pos2 + 1 < ps2.length && ps2[pos2+1].sum+arr1.sum < 100) {
        pos2++;
    }
    for (var i = pos2; i >= 0; i--) {
        result.push(arr1.concat(ps2[i]));
    }
    pos1++;
}

工作基准将此与非拆分解决方案进行比较

1. 此解决方案的决策版本(告诉您,是否有解决方案？)在O(2 ^(N/2))时间内运行.我希望如果存在O(1)解,则在O(2 ^(N/2))中运行,并且在每个子集是解的最坏情况下,O(2 ^ N)时间(与未优化相同).在我的测试中,从0到99的随机数大小为20-50的列表上的因子为2-5更快(加速与大小成正比,但我不确定通过什么公式).

Answer 2

所以如果你有一组数字:

var arr = [2, 25, 37, 54, 54, 76, 88, 91, 99]

首先将数组过滤到小于100的数组

var filtered = arr.filter(function(val){ return val < 100; });

现在您需要找到这些数字的幂集.

它看起来像有一个代码示例这里,将实现这一目标.

摘抄

function powerset(arr) {
    var ps = [[]];
    for (var i=0; i < arr.length; i++) {
        for (var j = 0, len = ps.length; j < len; j++) {
            ps.push(ps[j].concat(arr[i]));
        }
    }
    return ps;
}

所以你要接受

var powerSet = powerset(filtered);

而作为一些糖,您可以使用join很好地格式化结果

console.log('{' + powerSet.join('}{') + '}');

或者如果你真的希望它输出为一组所有集合,这在技术上会更正确:)

console.log('{ {' + powerSet.join('}{') + '} }');

这是一个工作演示

编辑

对不起,你想要总和小于100 的所有套装.肯尼贝克是对的.抛弃过滤的第一步,然后修改powerset方法,使用reduce快速查看数组的总和是否小于100:

function powerset(arr) {
    var ps = [[]];
    for (var i=0; i < arr.length; i++) {
        for (var j = 0, len = ps.length; j < len; j++) {
            var arrCandidate = ps[j].concat(arr[i]);
            if (arrCandidate.reduce(function(p, c){ return p + c; }) < 100)
                ps.push(arrCandidate);
        }
    }
    return ps;
}

这是一个更新的演示