javascript - 如何使用javascript将数字划分为数组中包含的特定值

Question

2我有以下数字数组和以下数字:

var array= [0.5, 1, 2, 3, 5, 10, 15, 20, 30, 40, 50, 100, 150, 250, 500];
var number = 1845;

“期望结果”--> [500, 500, 500, 250, 50, 40, 5]

我需要找到一种方法来得出上述数组中包含的数字的最佳组合，以便它们的相加创建给定的数字。该代码必须以这种方式工作，因为可接受的数字只是数组中的数字。因此，我需要返回 500,500,500,250,50,40,5，而不是 1845。

这是我的代码，但它没有按我的预期工作。

array = array.reverse();
var values = new Array();
var sts = $.inArray(number, array);
if (sts != -1){
    return number;
} else {
    for (k=0; k<array.length; k++){
        if ((number - array[k]) > 0){
            values.push(array[k]);
            number = number - array[k];
        }
    }
    return values.toString();
}

Answer 1

该提案迭代给定项目的所有可能组合，并使用一些短路来减少迭代/递归。

如果右侧(潜在结果集)的总和大于所需的总和，并且所有项目(左侧和右侧)的总和小于所需的总和，则停止。

function getParts(array, sum) {
    function add(a, b) { return a + b; }

    function iter(left, right) {
        var sumRight = right.reduce(add, 0);
        left = left.slice();
        if (sumRight >= sum) {
            sumRight === sum && result.push(right);
            return;
        }
        if (!left.length || left.reduce(add, 0) + sumRight < sum) {
            return;
        }
        iter(left, right.concat(left.pop()));
        iter(left, right.concat([]));
    }

    var result = [];
    iter(array, []);
    result.sort(function (a, b) { return a.length - b.length; });
    return result;
}

function print(o) {
    document.write('<pre>length: ' + o.length + ' ' + JSON.stringify(o, 0, 4) + '</pre>');
}

print(getParts([0.5, 1, 2, 3, 5, 10, 15, 20, 30, 40, 50, 100, 150, 250], 5000));
print(getParts([0.5, 1, 2, 3, 5, 10, 15, 20, 30, 40, 50, 100, 150, 250], 495));