javascript - 按百分比从数字数组中抽取

Question

让我们举一个充满大于 0 的数字的数组的例子:

let prices = [10,6200,20,20,350,900,26,78,888,10000,78,15000,200,1280,2000,450];

在我们添加所有数字并获得总金额(例如它是 33770)之后，我们想从这个总金额中取出一些 %(部分)。假设 5% (1689)。

我们的输出将是第一个数组中的最佳候选数组。当然，该值不必正好是 5%，但它不能超过 5%，并且它必须包含尽可能大的数字。

我试图做一些算法，但它是不可预测的，而且非常不准确。

编辑:我想到了使用包容和排除原则。可以帮忙吗？

Answer 1

基本上，您可以将索引处的元素添加到临时数组，也可以不添加。然后，检查索引是否达到数组长度或总和是否大于想要的总和。然后，检查总和并将临时数组添加到结果集中，或者不。最后，继续直到所有索引都被访问。

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

    function fork(i, t) {
        var r = (result[0] || []).reduce(add, 0),
            s = t.reduce(add, 0);
        if (i === array.length || s > sum) {
            if (s <= sum && t.length && r <= s) {
                if (r < s) {
                    result = [];
                }
                result.push(t);
            }
            return;
        }
        fork(i + 1, t.concat([array[i]]));
        fork(i + 1, t);
    }

    var result = [];
    fork(0, []);
    return result;
}

var result = getCombinations([10, 6200, 20, 20, 350, 900, 26, 78, 888, 10000, 78, 15000, 200], 1689)

console.log(result[0].reduce((a, b) => a + b));
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }