获取等于目标的数组项的总和(子集总和) [英] Get the sum of array items that are equal to the target (Subset sum)
问题描述
我需要获取等于目标的数组项的总和.如果数组项目的总和不等于目标,我希望获得小于目标的最高总和.
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: http://jsfiddle.net/kUELD/
JSFiddle: http://jsfiddle.net/kUELD/
这篇关于获取等于目标的数组项的总和(子集总和)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!