Problems in real life may be abstracted into such a data model:
Select several numbers from an array so that the sum of these numbers is the specified value.
Most readers should have had the experience of online shopping. Online shopping usually has a function to collect orders. If the reader buys a product of 70 yuan, but the purchase must exceed 100 yuan to get free shipping, the system will automatically recommend some products. It costs almost 100 yuan.
How does the system determine which products to recommend? This is actually the model just mentioned. We can put the prices of hot-selling products into an array, and then use an algorithm to find out which prices in the array add up to 30 yuan.
Without further ado, Xiaocai will share with you a JavaScript version of the algorithm implementation.
Algorithm code:
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; }
Calling instructions:
array: data source array. Required.
sum: sum added. Required.
tolerance: Tolerance. If this parameter is not specified, the sum must be equal to the sum parameter. Specifying this parameter allows the result to float within the tolerance range. Optional.
targetCount: Number of operands. If this parameter is not specified, the result will include all possible situations. Specifying this parameter can filter out the addition of a fixed number of numbers. If it is specified as 3, the result will only include the addition of three numbers. Optional.
Return value: What is returned is an array within an array structure. The elements in the inner array are the operands, and the elements in the outer array are all possible results.