我有一个数组,它总是有6个键:var ary = [5,10,28,50,56,280]
。我有一个定义为limit
的变量,我想对照它进行检查。
我想从这个高于limit
的数组中找到最低可能的键组合或键和。我们称之为result
。
我试图在以下限制条件下工作:
1result
本身可以是单个密钥:例如如果limit = 0
,则最低可能的密钥组合或密钥之和应当默认为它能够找到的最低密钥,该最低密钥将是ary[ 0 ]
。在这种情况下为CCD_ 8。
2result
可以是任意键的组合:如果limit = 11
,则result
将=ary[ 0 ] + ary[ 1 ]
(5+10(。即CCD_ 13。
3最后,result
可以高于ary
的最大和:result = 5 + 10 + 28 + 50 + 56 + 280; // equals 429
在这种情况下,限制为430
注意:在超过result
之前,任何键都可以重复多次。
我的尝试正在进行中:
function add(a, b) { //add all keys in array
return a + b;
}
var combine = function(a, min) { //find all combinations of array
var fn = function(n, src, got, all) {
if (n == 0) {
if (got.length > 0) {
all[all.length] = got;
}
return;
}
for (var j = 0; j < src.length; j++) {
fn(n - 1, src.slice(j + 1), got.concat([src[j]]), all);
}
return;
}
var all = [];
for (var i = min; i < a.length; i++) {
fn(i, a, [], all);
}
all.push(a);
return all;
}
var subsets = combine([5,10,28,50,56,280], 1);
var limit = 11;
for( var i = 0; i < subsets.length; i++ ){
document.write('combination: ' + subsets[ i ] + ' sum: ' + subsets[ i ].reduce(add, 0) + '<br>');
}
I认为这是有效的。你能提供更多的测试用例吗?您的答案中预期的429 > 434
应该是429 > 430
,对吧?
var findLowest = function(arr, limit) {
if (limit < arr[0]) return arr[0];
// If there's a number in our arr that's higher than the limit,
// this is the initial benchmark
var bestCandidate = Infinity,
maxIndex = arr.findIndex(v => v > limit);
if (maxIndex !== -1) {
bestCandidate = arr[maxIndex] - limit;
arr = arr.slice(0, maxIndex);
}
// Calculate remainders, call this method recursively for all remainders
var diffs = arr.map(v => limit % v);
var finalDiffs = diffs.map(v => findLowest(arr, v) - v);
return limit + Math.min(bestCandidate, finalDiffs.sort()[0]);
};
var prepareData = function(arr) {
return arr
// Remove duplicates of nrs in array
.reduce((res, v) => {
var needed = !res.length || res.every(r => v % r);
return needed ? res.concat(v) : res;
}, [])
// Generate each combination (length * length - 1)
.reduce((res, v, i, all) => {
return res.concat(v).concat(all.slice(i + 1).map(v2 => v + v2));
}, [])
// Sort lowest first
.sort((a, b) => a - b);
}
var data = [5,10,28,50,56,280];
var testCases = [
[data, 5, 10],
[data, 11, 15],
[data, 25, 28],
[data, 50, 53],
[data, 55, 56],
[data, 1, 5],
[data, 281, 282], // 9 * 28 + 5 * 6
[[50, 60, 110], 161, 170]
];
testCases.forEach(tc => {
var prep = prepareData(tc[0]);
var result = findLowest(prep, tc[1]);
if (result !== tc[2]) {
console.log("Limit: ", tc[1]);
console.log("Expected: ", tc[2]);
console.log("Result: ", result);
console.log("----");
}
});
注意:我当前的尝试是递归的,这可能不理想。。。如果它通过了您的所有测试,我们可以将其重写为非递归。
因此,这里有一个使用嵌套forEach
循环的解决方案:
var ary = [5, 10, 28, 50, 56, 280];
function lowestSum(limit) {
var thisArg = {sum: 0};
ary.forEach(function(ele1, index1) {
if (ele1 > limit && (ele1 < this.sum || this.sum === 0))
this.sum = ele1;
ary.forEach(function(ele2, index2) {
if (index1 !== index2 && ele1 + ele2 > limit
&& (ele1 + ele2 < this.sum || this.sum === 0)) {
this.sum = ele1 + ele2;
}
}, this);
}, thisArg);
return thisArg.sum;
}
console.log(lowestSum(6));
console.log(lowestSum(11));
console.log(lowestSum(27));
console.log(lowestSum(28));
如果您有一个小数组,因此不太关心效率,那么您可以执行以下操作。
- 生成候选对
- 根据候选配对的总和对其进行排序
-
循环浏览已排序的配对,直到找到一个超出限制的
var limit = 39; var ary = [5,10,28,50,56,280]; function getLowestCombinationOverLimit(ary, limit) { var i, j, p; var pairs = []; for(i = 0; i < ary.length; i++) { for(j = i + 1; j < ary.length; j++) { pairs.push({x:ary[i], y:ary[j]}); } } pairs.sort(function (a, b) { return (a.x + a.y) - (b.x + b.y); }); for (i = 0; i < pairs.length; i++) { p = pairs[i]; if (p.x + p.y > limit) { return p; } } return null; } console.log(getLowestCombinationOverLimit(ary, limit));
- 对数组进行排序
- 首先迭代数组的最大值,从极限值中减去最接近的值,直到极限值低于0
function calcSumOfLowestComponents(ary,limit){
ary.sort(function(a,b) {
return a - b;
});
var safeCount = 0;
var components = [];
var remainder = limit + 1;
while (remainder > 0){
var found = false;
for( var i = ary.length - 1 ; i >= 0; i-- ){
if (remainder > ary[ i ]){
var closeHigh = i != ary.length - 1 ? ary[i + 1] : ary[i];
var closeLow = ary[i];
if (closeHigh - remainder > remainder - closeLow){
components.push(closeLow);
remainder -= closeLow;
}
else{
components.push(closeHigh);
remainder -= closeHigh;
}
found = true;
}
}
if (!found && remainder > 0){
components.push(ary[ 0 ]);
remainder -= ary[ 0 ];
}
if (safeCount > 1000){
break;
}
safeCount++;
}
return { total : limit + 1 - remainder, components : components};
}
function dumpData(array,value){
var result = calcSumOfLowestComponents(array,value);
document.write("Value = " + value + " Total = " + result.total + " Components " + result.components + "</br>");
}
var array = [5,10,28,50,56,280];
dumpData(array,2);
dumpData(array,5);
dumpData(array,11);
dumpData(array,25);
dumpData(array,28);
dumpData(array,50);
dumpData(array,55);
dumpData(array,281);
dumpData(array,429);
结果
Value = 2 Total = 5 Components 5
Value = 5 Total = 10 Components 5,5
Value = 11 Total = 15 Components 10,5
Value = 25 Total = 28 Components 28
Value = 28 Total = 33 Components 28,5
Value = 50 Total = 55 Components 50,5
Value = 55 Total = 56 Components 56
Value = 281 Total = 285 Components 280,5
Value = 429 Total = 430 Components 280,56,56,28,10