算法：从数组中找出最佳的组合

搜索

您当前位置：首页 > 文章中心 > 网页编程 > Javascript

【Javascript】

下载

新闻

文章

求一算法，从数组中找出最佳的组合。如从数组 [ 42.6,140.4,60.2,46.8,11.2,106.6,57,75,47.6,90.2,115.2] 中找到累计值最接近 600 （ >=600 ）的组合

“求一算法，从数组中找出最佳的组合。如从数组 [ 42.6,140.4,60.2,46.8,11.2,106.6,57,75,47.6,90.2,115.2] 中找到累计值最接近 600 （ >=600 ）的组合”

这是论坛里提出的一个要求。我们先来看一种算法：

var original_array = [42.6,140.4,60.2,46.8,11.2,106.6,57,75,47.6,90.2,115.2];
    var result = [];
    var condition = 600;
    main(original_array);
    console.log(result);
    console.log(result[0]);
    function main(array){
        for(var i =0; i < array.length; i++){
            process(0,array.slice(i,array.length),[]);
        }
        result.sort(function(a,b){
            return a.Total - b.Total;
        });
    }
    function process(num,array1,array2){
        if(num >= condition){
            result.push({Total:num,Array:array2});
            if(array1.length > 0){
                var value = array2[array2.length - 1];
                num -= value;
                process(num,array1,array2.slice(0,array2.length - 1));
            }
        }else{
            if(array1.length > 0){
                var value = array1[0];
                num += value;
                array2.push(value);
                process(num,array1.slice(1,array1.length),array2);
            }
        }
    }

只看代码可能不能明白它的过程，我简单介绍下：
从原数组第一位取所有元素组成第一组，从第二位取所有元素组成第二组……如此反复共分成Array.length组。然后循环新数组内元素相加，如果和大于或者等于600就取出来又组成新数组，最后新数组升序排序下，第一个就当着是符合的组合。看似没什么，其实漏洞百出。

第一：这是一个组合问题，假如原数组只有一个元素共可组成1组，如果数组有2个元素共可组成3组（a,b,ab）假如是N组呢？绝对不是作者认为的只有N组。

第二：二次分成新数组内按顺序累加并判断超出指定数就取出，这也是错误的，因为这并没有达到最初条件：找最佳组合，其实也是问题一的原因。举个简单例子：

var original_array = [550,42,10,300,301,200,121,50];
//找出的结果是 [300,301] 这明显不对。正确应该是[550,50]
var original_array = [550,42.6,140.4,60.2,46.8,11.2,106.6,57,75,47.6,90.2,115.2,322,155,121,50];
//找出的结果是 [550, 42.6, 11.2] 这也是错误。

第三：这种分组有可能存在几个并列最佳的组合，也就是说应该返回至少一个以上组合。就算所有加起来都达到600，那么整个数组也算是一个组合。

话说回来，其实这就是一个任意位数组合的问题，不考虑排序的位置，而且假设数组任意元素不同来处理，我们先来解决在一个数组内指定N个元素可以组成多少个组合问题先解决：

    function group(a, len, result){
        //返回一个数组由len个元素组成的各个组合
        result = result || [];
        var arr = a.slice(0);
        var item = [arr.shift()];
        (function func(item,arr){
            var itemc,temp = arr.slice(0),l = len - item.length;
            if( l == 0){
                result.push(item);//放入结果
            }else if( l == 1){
                for(var j in arr){
                    itemc = item.slice(0);
                    itemc.push(arr[j]);
                    result.push(itemc);
                }
            }else if( l > 1){
                itemc = item.slice(0);
                itemc.push(temp.shift());
                func(itemc,temp);
                item.length + temp.length >= len && func(item,temp);
            }
        })(item,arr);
        return arr.length < len ? result : group(arr, len, result);
    }

由此函扩展，我们把一个N个元素的数组数，把它1位、2位、3位……N位组合都提取出来合并组成一个新数组，那么最佳组合就在其中了。修改得出：

    function group(a, len){
        var arr = a.slice(0);
        var item = [arr.shift()];
        (function func(item,arr){
            var itemc,temp = arr.slice(0),l = len - item.length;
            if( l == 0){
                result.push(item);//放入结果
            }else if( l == 1){
                for(var j in arr){
                    itemc = item.slice(0);
                    itemc.push(arr[j]);
                    result.push(itemc);
                }
            }else if( l > 1){
                itemc = item.slice(0);
                itemc.push(temp.shift());
                func(itemc,temp);
                item.length + temp.length >= len && func(item,temp);
            }
        })(item,arr);
        arr.length >= len && group(arr, len);
    }
    //求一个数组内所有元素和
    function sum(arr){
        var s=0;
        for(var k in arr)s+=arr[k];
        return s;
    }
    var arr = [],narr=[],result=[],k,raw = [550,42.6,140.4,60.2,46.8,11.2,10,600,75,604,90.2,115.2,322,155,121,50];
    for(var i=raw.length;i--;){
        k=raw[i];//先剔除不小于600的数，直接放入结果，又可减少组合。
        k >= 600 ? result.push([k]) : arr.push(k);
    }
    for(i=arr.length+1;--i;){
        group(arr, i);//得出所有组合
    }
    //剔除不符合条件的元素
    for(i=result.length;i--;){
        k=sum(result[i]);
        k >= 600 && narr.push(result[i]);
    }
    narr.sort(function(a,b){
        return sum(a)<sum(b);//重排数组,数组多sort非常耗资源，看需求是否重排。
    });
    console.log(narr);//得到任意组合的数组并由大到小排序,数组已经上万个