現(xiàn)實生活中的問題，可能會抽象為這樣一種數(shù)據(jù)模型：
從一個數(shù)組中挑選出幾個數(shù)，讓這幾個數(shù)相加的和為指定的值。
大多數(shù)讀者應(yīng)該有過網(wǎng)購的經(jīng)歷，網(wǎng)購一般會有個湊單功能，假如讀者買了70元的商品，但是必須滿100元才能包郵，這時系統(tǒng)會自動推薦一些商品，加起來差不多就100塊錢了。
系統(tǒng)如何確定推薦哪些商品呢？這其實就是剛剛提到的模型，我們可以把熱銷商品的價格放到一個數(shù)組中，然后利用算法，找出數(shù)組中哪些價格的和為30元。
廢話少說，小菜給大家分享一個JavaScript版本的算法實現(xiàn)。
算法代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
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;} |
調(diào)用說明：
array: 數(shù)據(jù)源數(shù)組。必選。
sum: 相加的和。必選。
tolerance: 容差。如果不指定此參數(shù)，則相加的和必須等于sum參數(shù)，指定此參數(shù)可以使結(jié)果在容差范圍內(nèi)浮動。可選。
targetCount: 操作數(shù)數(shù)量。如果不指定此參數(shù)，則結(jié)果包含所有可能的情況，指定此參數(shù)可以篩選出固定數(shù)量的數(shù)相加，假如指定為3，那么結(jié)果只包含三個數(shù)相加的情況?？蛇x。
返回值：返回的是數(shù)組套數(shù)組結(jié)構(gòu)，內(nèi)層數(shù)組中的元素是操作數(shù)，外層數(shù)組中的元素是所有可能的結(jié)果。
