javascript - 如何在数组中找到最小可能的键组合

Question

我有一个始终有 6 个键的数组:var ary = [5,10,28,50,56,280] 。我有一个变量定义为 limit我想检查一下。

我想从这个数组中找到 limit 以上的最低可能组合或键总和。我们称之为result .

我试图在其中工作的一些限制:

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

2 result可以是任意键的组合:如果limit = 11 , result会= ary[ 0 ] + ary[ 1 ] (5+10)。这将是 15 .

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

注意:任何键都可以重复任意多次，直到超过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>');
}

Answer 1

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

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("----");
    }
});

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