現實生活中的問題,往往可以抽象為這樣的資料模型:從一個陣列中挑選出幾個數,讓這幾個數相加的和等於指定值。
大多數讀者應該都有過網購經歷。網購通常有湊單功能,假如你買了 70 元的商品,但必須滿 100 元才能包郵,這時系統會自動推薦一些商品,加起來差不多剛好 100 元。系統究竟如何確定推薦哪些商品呢?這正是本文要探討的模型——把熱銷商品的價格放進一個陣列,再利用演算法找出哪些價格的和等於目標值。
以下分享一個 JavaScript 版本的演算法實現:
function getCombBySum(array,sum,tolerance,targetCount){ var util = { 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; }, getArrayIndex: function(array) { var i = 0, r = []; for(i = 0;i<array.length;i++){ r.push(i); } return r; } },logic = { init: function(array,sum) { var _array = array.concat(), r = [], i = 0; _array.sort(function(a,b){ return a - b; }); for(i = 0;i<_array.length;i++){ if(_array[i]<=sum){ r.push(_array[i]); }else{ break; } } return r; }, core: function(array,sum,arrayIndex,count,r){ var i = 0, k = 0, combArray = [], _sum = 0, _cca = [], _cache = []; if(count == _returnMark){ return; } combArray = util.getCombination(arrayIndex,count); for(i = 0;i<combArray.length;i++){ _cca = combArray[i]; _sum = 0; _cache = []; 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; _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,指定後可使結果在容差範圍內浮動。
targetCount:運算數量,可選。若不指定則返回所有可能的情況,指定後可篩選出固定數量相加的結果。
回傳值為陣列套陣列的結構,內層陣列是運算數,外層陣列是所有可能的結果。