javascript - 获取等于目标的数组项的总和(子集总和)

Question

我需要获取等于目标的数组项的总和。如果数组项的总和不等于目标，我想获得小于目标的最高总和。

这是一个例子:

输入 [4, 6, 8, 12, 4, 6, 6, 12, 4, 4,4]

结果: [12] [12] [8, 4] [6, 6] [4,4,4] [6,4]

注意:数组项只能使用一次。

目前这是我现在拥有的:

    var subset_sum = function (items, target) {
    var results = [];

    items.sort(function (a, b) { return b - a });

    ss = function (items) {
        var item = items.shift();
        if (item < target) {
            var perms = [];
            perms.push(item);
            var isItemPush = false;

            var counter = 0
            var innerSubset = function () {
                if (item + items[counter] === target) {
                    perms.push(items[counter])
                    items.splice(counter, 1);
                    results.push(perms);
                    isItemPush = true;
                } else {
                    if (counter < items.length) {
                        counter += 1;
                        innerSubset();
                    }
                }
            }

            innerSubset();

        } else {
            results.push(item);
        }

        if (items.length === 0) {
            return results;
        }

        return ss(items);
    }
    return ss(items)
}

window.onload = function () {
    var items = [4, 6, 8, 12, 4, 6, 6, 12, 4, 4];
    target = 12;

    result = subset_sum(items, target);
    console.log(result);
}

这种方法的问题在于它只是一维或二维的。从上面的例子来看，它并没有返回结果 [4,4,4] 和 6。

Answer 1

与您的解决方案非常相似，有点不清楚是否有帮助:

numbers = [4, 6, 8, 12, 4, 6, 6, 12, 4, 4];

var result = createSubsets(numbers, 12);

console.log('Result', JSON.stringify(result));

function createSubsets(numbers, target) {
    // filter out all items larger than target
    numbers = numbers.filter(function (value) {
        return value <= target;
    });

    // sort from largest to smallest
    numbers.sort(function (a, b) {
        return b - a;
    });

    // array with all the subsets
    var result = [];

    while (numbers.length > 0) {
        var i;
        var sum = 0;
        var addedIndices = [];

        // go from the largest to the smallest number and
        // add as many of them as long as the sum isn't above target
        for (i = 0; i < numbers.length; i++) {
            if (sum + numbers[i] <= target) {
                sum += numbers[i];
                addedIndices.push(i);
            }
        }

        // remove the items we summed up from the numbers array, and store the items to result
        // since we're going to splice the numbers array several times we start with the largest index
        // and go to the smallest to not affect index position with splice.
        var subset = [];
        for (i = addedIndices.length - 1; i >= 0; i--) {
            subset.unshift(numbers[addedIndices[i]]);
            numbers.splice(addedIndices[i], 1);
        }
        result.push(subset);
    }

    return result;
}

产生数组:

[12],[12],[8,4],[6,6],[6,4],[4,4]

子集长度没有限制。如果您将 4 添加到数字数组中，您将得到结果:

[12],[12],[8,4],[6,6],[6,4],[4,4,4]

JSFiddle:http://jsfiddle.net/kUELD/