JavaScript implémente la sélection de n nombres dont la somme est égale à une valeur fixe à partir d'un tableau_javascript skills

Les problèmes de la vie réelle peuvent être résumés dans un tel modèle de données :

Sélectionnez plusieurs nombres dans un tableau afin que la somme de ces nombres soit la valeur spécifiée.

La plupart des lecteurs devraient avoir eu l'expérience des achats en ligne. Les achats en ligne ont généralement une fonction pour collecter les commandes. Si le lecteur achète un produit de 70 yuans, mais que l'achat doit dépasser 100 yuans pour bénéficier de la livraison gratuite, le système le fera automatiquement. Je recommande certains produits. Cela coûte près de 100 yuans.

Comment le système détermine-t-il les produits à recommander ? Il s'agit en fait du modèle que nous venons de mentionner. Nous pouvons regrouper les prix des produits les plus vendus dans un tableau, puis utiliser un algorithme pour découvrir quels prix dans le tableau totalisent 30 yuans.

Sans plus attendre, Xiaocai partagera avec vous une version JavaScript de l'implémentation de l'algorithme.

Code de l'algorithme :

function getCombBySum(array,sum,tolerance,targetCount){
var util = {
/*
get combination from array
arr: target array
num: combination item length
return: one array that contain combination arrays
*/
getCombination: function(arr, num) {
var r=[];
(function f(t,a,n)
{
if (n==0)
{
return r.push(t);
}
for (var i=0,l=a.length; i<=l-n; i++)
{
f(t.concat(a[i]), a.slice(i+1), n-1);
}
})([],arr,num);
return r;
},
//take array index to a array
getArrayIndex: function(array) {
var i = 0,
r = [];
for(i = 0;i<array.length;i++){
r.push(i);
}

return r;
}
},logic = {
//sort the array,then get what's we need
init: function(array,sum) {
//clone array
var _array = array.concat(),
r = [],
i = 0;
//sort by asc
_array.sort(function(a,b){
return a - b;
});
//get all number when it's less than or equal sum
for(i = 0;i<_array.length;i++){
if(_array[i]<=sum){
r.push(_array[i]);
}else{
break;
}
}

return r;
},
//important function
core: function(array,sum,arrayIndex,count,r){
var i = 0,
k = 0,
combArray = [],
_sum = 0,
_cca = [],
_cache = [];

if(count == _returnMark){
return;
}
//get current count combination
combArray = util.getCombination(arrayIndex,count);
for(i = 0;i<combArray.length;i++){
_cca = combArray[i];
_sum = 0;
_cache = [];
//calculate the sum from combination
for(k = 0;k<_cca.length;k++){
_sum += array[_cca[k]];
_cache.push(array[_cca[k]]);
}
if(Math.abs(_sum-sum) <= _tolerance){
r.push(_cache);
} 
}

logic.core(array,sum,arrayIndex,count-1,r);
}

},
r = [],
_array = [],
_targetCount = 0,
_tolerance = 0,
_returnMark = 0;

//check data
_targetCount = targetCount || _targetCount;
_tolerance = tolerance || _tolerance;

_array = logic.init(array,sum);
if(_targetCount){
_returnMark = _targetCount-1;
}

logic.core(_array,sum,util.getArrayIndex(_array),(_targetCount || _array.length),r);

return r;
}

Instructions d'appel :

array : tableau de sources de données. Requis.

somme : somme ajoutée. Requis.

tolérance : Tolérance. Si ce paramètre n'est pas spécifié, la somme doit être égale au paramètre sum La spécification de ce paramètre permet au résultat de flotter dans la plage de tolérance. Facultatif.

targetCount : nombre d'opérandes. Si ce paramètre n'est pas spécifié, le résultat inclura toutes les situations possibles. La spécification de ce paramètre peut filtrer l'ajout d'un nombre fixe de nombres. S'il est spécifié comme 3, le résultat inclura uniquement l'ajout de trois nombres. Facultatif.

Valeur de retour : ce qui est renvoyé est un tableau dans une structure de tableau. Les éléments du tableau interne sont les opérandes et les éléments du tableau externe sont tous des résultats possibles.