如何找到数组中键的最低组合 [英] How to find the lowest possible combination of keys within an array

问题描述

我有一个数组，该数组将始终具有6个键:var ary = [5,10,28,50,56,280]. 我有一个定义为limit的变量，要对其进行检查.

I have an array that will always have 6 keys: var ary = [5,10,28,50,56,280]. I have a variable defined as limit I want to check it against.

我想从此数组中找到limit以上的最低组合键或总和.我们将其称为result.

I want to find the lowest possible combination or sum of keys from this array that is above limit. We'll call this result.

我要在其中进行一些限制:

A bit of constraints I am trying to work within:

1 result本身可以是单个键: 例如，如果limit = 0可能的最低组合键或总和应默认为可以找到的最低键ary[ 0 ].在这种情况下还是5.

1 result can be a single key itself: Such as If limit = 0 the lowest possible combination or sum of keys should default to the lowest key it can find which would be ary[ 0 ]. in this case or 5.

2 result可以是任何键的组合: 如果limit = 11，result将= ary[ 0 ] + ary[ 1 ](5 + 10).就是15.

2 result can be a combination of any keys: If limit = 11, result would = ary[ 0 ] + ary[ 1 ] ( 5 + 10 ). which would be 15.

3 最后，result可以高于ary的最大和: result = 5 + 10 + 28 + 50 + 56 + 280; // equals 429在这种情况下，限制为430

3 And lastly, result can be above the greatest sum of ary: result = 5 + 10 + 28 + 50 + 56 + 280; // equals 429 In this case limit would be 430

注意:任何键都可以重复多次，直到超过result为止.

Note: Any key can be repeated as many times as it has to before it surpasses result.

我正在进行的尝试:

function add(a, b) { //add all keys in array
    return a + b;
}

var combine = function(a, min) { //find all combinations of array
    var fn = function(n, src, got, all) {
        if (n == 0) {
            if (got.length > 0) {
                all[all.length] = got;
            }
            return;
        }
        for (var j = 0; j < src.length; j++) {
            fn(n - 1, src.slice(j + 1), got.concat([src[j]]), all);
        }
        return;
    }
    var all = [];
    for (var i = min; i < a.length; i++) {
        fn(i, a, [], all);
    }
    all.push(a);
    return all;
}

var subsets = combine([5,10,28,50,56,280], 1);
var limit = 11;

for( var i = 0; i < subsets.length; i++ ){
  document.write('combination: ' + subsets[ i ] + ' sum: ' + subsets[ i ].reduce(add, 0) + '<br>');
}

推荐答案

我认为可行.您可以提供更多的测试用例吗?您的答案中预期的429 > 434应该是429 > 430，对吗?

I think this works. Can you provide more test cases? The expected 429 > 434 from your answer should be 429 > 430, right?

var findLowest = function(arr, limit) {
    if (limit < arr[0]) return arr[0];

    // If there's a number in our arr that's higher than the limit,
    // this is the initial benchmark
    var bestCandidate = Infinity,
        maxIndex = arr.findIndex(v => v > limit);

    if (maxIndex !== -1) {
        bestCandidate = arr[maxIndex] - limit;
        arr = arr.slice(0, maxIndex);
    }

    // Calculate remainders, call this method recursively for all remainders
    var diffs = arr.map(v => limit % v);

    var finalDiffs = diffs.map(v => findLowest(arr, v) - v);
    
    return limit + Math.min(bestCandidate, finalDiffs.sort()[0]);
    
};

var prepareData = function(arr) {
    return arr
        // Remove duplicates of nrs in array
        .reduce((res, v) => {
            var needed = !res.length || res.every(r => v % r);
            return needed ? res.concat(v) : res;
        }, [])

        // Generate each combination (length * length - 1)
        .reduce((res, v, i, all) => {
            return res.concat(v).concat(all.slice(i + 1).map(v2 => v + v2));
        }, [])
        
        // Sort lowest first
        .sort((a, b) => a - b);
}

var data = [5,10,28,50,56,280];
var testCases = [
    [data, 5, 10],
    [data, 11, 15],
    [data, 25, 28],
    [data, 50, 53],
    [data, 55, 56],
    [data, 1, 5],
    [data, 281, 282], // 9 * 28 + 5 * 6
    [[50, 60, 110], 161, 170]
];

testCases.forEach(tc => {
    var prep = prepareData(tc[0]);
    var result = findLowest(prep, tc[1]);

    if (result !== tc[2]) {
      console.log("Limit: ", tc[1]);
      console.log("Expected: ", tc[2]);
      console.log("Result: ", result);
      console.log("----");
    }
});

注意:我当前的尝试是递归的，这可能并不理想...如果它通过了所有测试，我们可以将其重写为非递归的.

Note: my current try is recursive, which might not be ideal... If it passes all your tests, we could rewrite it to not be recursive.

这篇关于如何找到数组中键的最低组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！