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

本文介绍了获取等于目标的数组项的总和(子集总和)的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

I need to get the sum of array items that are equal to the target. If the sum of array item will not equal to the target I would like to get the highest sum that is less than the target.

这里是一个例子:

输入:[4、6、8、12、4、6、6、12、4、4、4]

Input: [4, 6, 8, 12, 4, 6, 6, 12, 4, 4,4]

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

Results: [12] [12] [8, 4] [6, 6] [4,4,4] [6,4]

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

Note: The array item can only be used once.

目前这是我现在拥有的:

Currently here is what I have right now:

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.

The problem with this approach is that it is only one or two dimensional. From the example above, it does not return the result [4,4,4] and 6.

推荐答案

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

Very similar solution to yours, a bit unclear if it's helpful:

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，则会得到结果:

There's no limit regarding the subset length. If you add one more 4 to the numbers array you will get result:

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

JSFiddle: jsfiddle/kUELD/

JSFiddle: jsfiddle/kUELD/