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

稿件来源: 阳光企业网站管理系统   撰稿作者: 太阳光   发表日期: 2014-05-05   阅读次数: 165   查看权限: 游客查看

求一算法,从数组中找出最佳的组合。如从数组 [ 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);//得到任意组合的数组并由大到小排序,数组已经上万个

 

关键词: js,算法,组合   编辑时间: 2014-05-06 10:36:24

  • 感到高兴

    0

    高兴
  • 感到支持

    0

    支持
  • 感到搞笑

    0

    搞笑
  • 感到不解

    0

    不解
  • 感到谎言

    0

    谎言
  • 感到枪稿

    0

    枪稿
  • 感到震惊

    0

    震惊
  • 感到无奈

    0

    无奈
  • 感到无聊

    0

    无聊
  • 感到反对

    0

    反对
  • 感到愤怒

    0

    愤怒
0%(0)
0%(0)
共有0 条评论 发言请遵守【相关规定

网友评论

会员头像
发 表同步腾讯微博    验证码:  点击更新请先登陆
  • 暂无评论
关闭模块文章图片 article Pictrue
  • 我的妈妈爸爸
  • 基于koa2+mysql+vue2.0+Element阳光内容管理系统
  • 代码覆盖率工具 Istanbul 入门教程
  • 全栈工程师的武器——MEAN
  • 9款超炫的 CSS3 复选框(Checkbox)
  • 微信开发在线翻译功能
  • CSS3那些不为人知的高级属性
  • 给easyui的datebox添加清空事件
  • flash写字效果
  • kendoUI系列教程之DropDownList下拉菜单
  • kendoUI系列教程之datetimepicker日期时间选择
  • kendoUI系列教程之datepicker日期选择
  • kendoUI系列教程之combobox下拉列表框
  • kendoUI系列教程之colorpicker
  • kendoUI系列教程之calendar日历表
  • kendoUI系列教程之autocomplete自动补齐