現實生活中的問題,可能會抽象為這樣一種數據模型:
從一個數組中挑選出幾個數,讓這幾個數相加的和為指定的值。
大多數讀者應該有過網購的經歷,網購一般會有個湊單功能,假如讀者買了70元的商品,但是必須滿100元才能包郵,這時系統會自動推薦一些商品,加起來差不多就100塊錢了。
系統如何確定推薦哪些商品呢?這其實就是剛剛提到的模型,我們可以把熱銷商品的價格放到一個數組中,然后利用算法,找出數組中哪些價格的和為30元。
廢話少說,小菜給大家分享一個JavaScript版本的算法實現。
算法代碼:
function getCombBySum(array,sum,tolerance,targetCount){var util = {/*get combination from arrayarr: target arraynum: combination item lengthreturn: 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 arraygetArrayIndex: 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 needinit: function(array,sum) {//clone arrayvar _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 sumfor(i = 0;i<_array.length;i++){if(_array[i]<=sum){r.push(_array[i]);}else{break;}}return r;},//important functioncore: function(array,sum,arrayIndex,count,r){var i = 0,k = 0,combArray = [],_sum = 0,_cca = [],_cache = [];if(count == _returnMark){return;}//get current count combinationcombArray = util.getCombination(arrayIndex,count);for(i = 0;i<combArray.length;i++){_cca = combArray[i];_sum = 0;_cache = [];//calculate the sum from combinationfor(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;}
調用說明:
array: 數據源數組。必選。
sum: 相加的和。必選。
tolerance: 容差。如果不指定此參數,則相加的和必須等于sum參數,指定此參數可以使結果在容差范圍內浮動??蛇x。
targetCount: 操作數數量。如果不指定此參數,則結果包含所有可能的情況,指定此參數可以篩選出固定數量的數相加,假如指定為3,那么結果只包含三個數相加的情況??蛇x。
返回值:返回的是數組套數組結構,內層數組中的元素是操作數,外層數組中的元素是所有可能的結果。
新聞熱點
疑難解答