JavaScript implementiert die Auswahl von n Zahlen, deren Summe einem festen Wert aus einem Array_Javascript-Fähigkeiten entspricht

Probleme im wirklichen Leben können in ein solches Datenmodell abstrahiert werden:

Wählen Sie mehrere Zahlen aus einem Array aus, sodass die Summe dieser Zahlen dem angegebenen Wert entspricht.

Die meisten Leser sollten die Erfahrung des Online-Shoppings gemacht haben. Wenn der Leser ein Produkt im Wert von 70 Yuan kauft, muss der Kaufpreis 100 Yuan überschreiten, um kostenlosen Versand zu erhalten Ich empfehle einige Produkte. Es kostet fast 100 Yuan.

Wie ermittelt das System, welche Produkte empfohlen werden? Dies ist eigentlich das gerade erwähnte Modell. Wir können die Preise der meistverkauften Produkte in ein Array einfügen und dann mithilfe eines Algorithmus herausfinden, welche Preise im Array 30 Yuan ergeben.

Ohne weitere Umschweife wird Xiaocai Ihnen eine JavaScript-Version der Algorithmusimplementierung zur Verfügung stellen.

Algorithmuscode:

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;
}

Anrufanweisungen:

Array: Datenquellenarray. Erforderlich.

Summe: Summe hinzugefügt. Erforderlich.

Toleranz: Toleranz. Wenn dieser Parameter nicht angegeben ist, muss die Summe dem Summenparameter entsprechen. Durch die Angabe dieses Parameters kann das Ergebnis innerhalb des Toleranzbereichs schweben. Optional.

targetCount: Anzahl der Operanden. Wenn dieser Parameter nicht angegeben ist, umfasst das Ergebnis alle möglichen Situationen. Durch die Angabe dieses Parameters kann die Addition einer festen Anzahl von Zahlen herausgefiltert werden. Wenn er als 3 angegeben wird, umfasst das Ergebnis nur die Addition von drei Zahlen. Optional.

Rückgabewert: Was zurückgegeben wird, ist ein Array innerhalb einer Array-Struktur. Die Elemente im inneren Array sind die Operanden und die Elemente im äußeren Array sind alle möglichen Ergebnisse.