首页 > 代码库 > 从数组中选出和等于固定值的n个数(JavaScript实现)
从数组中选出和等于固定值的n个数(JavaScript实现)
现实生活中的问题，可能会抽象为这样一种数据模型：
从一个数组中挑选出几个数，让这几个数相加的和为指定的值。
大多数读者应该有过网购的经历，网购一般会有个凑单功能，假如读者买了70元的商品，但是必须满100元才能包邮，这时系统会自动推荐一些商品，加起来差不多就100块钱了。
系统如何确定推荐哪些商品呢？这其实就是刚刚提到的模型，我们可以把热销商品的价格放到一个数组中，然后利用算法，找出数组中哪些价格的和为30元。
废话少说，小菜给大家分享一个JavaScript版本的算法实现。
算法代码：
1 function getCombBySum(array,sum,tolerance,targetCount){ 2 var util = { 3 /* 4 get combination from array 5 arr: target array 6 num: combination item length 7 return: one array that contain combination arrays 8 */ 9 getCombination: function(arr, num) { 10 var r=[]; 11 (function f(t,a,n) 12 { 13 if (n==0) 14 { 15 return r.push(t); 16 } 17 for (var i=0,l=a.length; i<=l-n; i++) 18 { 19 f(t.concat(a[i]), a.slice(i+1), n-1); 20 } 21 })([],arr,num); 22 return r; 23 }, 24 //take array index to a array 25 getArrayIndex: function(array) { 26 var i = 0, 27 r = []; 28 for(i = 0;i<array.length;i++){ 29 r.push(i); 30 } 31 32 return r; 33 } 34 },logic = { 35 //sort the array,then get what‘s we need 36 init: function(array,sum) { 37 //clone array 38 var _array = array.concat(), 39 r = [], 40 i = 0; 41 //sort by asc 42 _array.sort(function(a,b){ 43 return a - b; 44 }); 45 //get all number when it‘s less than or equal sum 46 for(i = 0;i<_array.length;i++){ 47 if(_array[i]<=sum){ 48 r.push(_array[i]); 49 }else{ 50 break; 51 } 52 } 53 54 return r; 55 }, 56 //important function 57 core: function(array,sum,arrayIndex,count,r){ 58 var i = 0, 59 k = 0, 60 combArray = [], 61 _sum = 0, 62 _cca = [], 63 _cache = []; 64 65 if(count == _returnMark){ 66 return; 67 } 68 //get current count combination 69 combArray = util.getCombination(arrayIndex,count); 70 for(i = 0;i<combArray.length;i++){ 71 _cca = combArray[i]; 72 _sum = 0; 73 _cache = []; 74 //calculate the sum from combination 75 for(k = 0;k<_cca.length;k++){ 76 _sum += array[_cca[k]]; 77 _cache.push(array[_cca[k]]); 78 } 79 if(Math.abs(_sum-sum) <= _tolerance){ 80 r.push(_cache); 81 } 82 } 83 84 logic.core(array,sum,arrayIndex,count-1,r); 85 } 86 87 }, 88 r = [], 89 _array = [], 90 _targetCount = 0, 91 _tolerance = 0, 92 _returnMark = 0; 93 94 //check data 95 _targetCount = targetCount || _targetCount; 96 _tolerance = tolerance || _tolerance; 97 98 _array = logic.init(array,sum); 99 if(_targetCount){100 _returnMark = _targetCount-1;101 }102 103 logic.core(_array,sum,util.getArrayIndex(_array),(_targetCount || _array.length),r);104 105 return r;106 }
调用说明：
array: 数据源数组。必选。
sum: 相加的和。必选。
tolerance: 容差。如果不指定此参数，则相加的和必须等于sum参数，指定此参数可以使结果在容差范围内浮动。可选。
targetCount: 操作数数量。如果不指定此参数，则结果包含所有可能的情况，指定此参数可以筛选出固定数量的数相加，假如指定为3，那么结果只包含三个数相加的情况。可选。
返回值：返回的是数组套数组结构，内层数组中的元素是操作数，外层数组中的元素是所有可能的结果。
原创内容，转载注明出处！
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。