我有一个数组,看起来像这样:
var x = 17;
var arr = [{ value:2, quantity: 4 }, { value:8, quantity: 1 }, { value:3, quantity: 3 }];
我的问题是如何查找那些元素的索引,这些元素的值加起来等于x
。在这种情况下,返回结果应为:
[1, 3, 3, 3]
当然,也可以使用
[0, 0, 0, 1, 2]
或[0, 0, 0, 0, 2, 2, 2]
来完成,但是返回数组长度越短越好。我有一个数组,看起来像这样:
var x = 17;
var arr = [{ value:2, quantity: 4 }, { value:8, quantity: 1 }, { value:3, quantity: 3 }];
我的问题是如何查找那些元素的索引,这些元素的值加起来等于x
。在这种情况下,返回结果应为:
[1, 3, 3, 3]
[0, 0, 0, 1, 2]
或[0, 0, 0, 0, 2, 2, 2]
来完成,但是返回数组长度越短越好。有更高效的方法来做这件事,但这是一个非常明显/干净的解决方案。我们将把它视为一个线性方程,其中combo
包含arr
中每个值的系数:
// your initial x and arr
var x = 17;
var arr = [{ value:2, quantity: 4 }, { value:8, quantity: 1 }, { value:3, quantity: 3 }];
// maximums[i] is the maximum amount of arr[i]'s you can ever
// have in any combination
var maximums = arr.map(function(item){ return Math.floor(x / item.value) });
// an array of the current coefficients we're trying. combo[i]
// corresponds to the coefficient for arr[i]
// we will start off with all coefficients set to 0 and
// increase each one by 1 as we go along
var combo = arr.map(function(){ return 0 });
// the sum we get with the current coefficients
var sum = 0;
// take the current coefficients in combo and try the next
// coefficient from left-to-right, we know when to stop
// trying to increase a given coefficient when it exceeds
// its corresponding value in the maximums array
function next() {
for(var i = 0; i < combo.length; i++) {
combo[i]++;
// we increased the coeff. so increase the sum
sum += arr[i].value;
if(combo[i] <= maximums[i]) {
// the coefficient is smaller/equal to its max size, so we're done
break;
}else{
// we've maxed out the right most coeff. so bail
if(i == combo.length-1) return false;
// reset this coefficient, remove it from sum & cont. loop
sum -= arr[i].value * combo[i];
combo[i] = 0;
}
}
return true;
}
// now we just enumerate all combinations until the sum equals x
while(next()) {
if(sum == x) break;
}
// if no combination is found, abort
if(sum != x) {
console.log('not possible');
// otherwise print the combination that works
}else{
for(var i = 0; i < combo.length; i++) {
if(combo[i] == 0) continue;
console.log(combo[i] + ' of (' + JSON.stringify(arr[i]) + ')');
}
}
如果您总是想要最小可能的组合,可以这样做:
function coeffsUsed() {
var count = 0;
for(var i = 0; i < combo.length; i++) {
if(combo[i] > 0) count++;
}
return count;
}
// now we just enumerate all combinations until the sum equals x
var smallestCombo = {};
var smallest = -1;
while(next()) {
if(sum == x) {
var count = coeffsUsed();
if(smallest == -1 || count < smallest) {
smallest = count;
smallestCombo = combo.slice(0); // clones the array
}
}
}
// if no combination is found, abort
if(smallest == -1) {
console.log('not possible');
// otherwise print the combination that works
}else{
for(var i = 0; i < smallestCombo.length; i++) {
if(smallestCombo[i] == 0) continue;
console.log(smallestCombo[i] + ' of (' + JSON.stringify(arr[i]) + ')');
}
}
arr
数组是不可预测的。 - Kasper Seweryn