mumu_chencl
2018-04-26 03:07
采纳率: 100%
浏览 3.5k
已采纳

求一组int类型数组中,任意数相加等于一个定值的高性能算法

如有数组{15, 25, 30, 35, 45,50, 55, 70, 80, 100}
,求任意数(n个元素)相加,和等于150的所有组合(组合的元素个数可进行手动控制)。

单个元素在组合中可以重复出现,
出现的结果可能有:
15+35+45+55
50+70+80
50+100
50+50+50

现在有一个这样一个方法,但是计算出来的最终结果只能满足部分条件,而且当元素的个数偏多的时候会造成溢出的情况。请各位大牛指点一下,如果有更好的算法请指教
private List SeveralCut(List prodWides, double mateWide, double addValue)
{
List planList = new List();

        if (prodWides.Count <= 0)
        {
            return planList;
        }

        for (int  i = 1; i < 1 << prodWides.Count; i++)//从1循环到2^N
        {
            double  sum = 0;
            string planStr = string.Empty;
            for (int j = 0; j < prodWides.Count; j++)
            {
                if ((i & 1 << j) != 0)//用i与2^j进行位与运算,若结果不为0,则表示第j位不为0,从数组中取出第j个数
                {
                    sum += prodWides[j];
                    planStr += prodWides[j] + "+";
                }
            }

            if (sum == mateWide -addValue)
            {
                Console.WriteLine(planStr.TrimEnd('+'));//如果和为所求,则输出
                planList.Add(planStr.TrimEnd('+'));
            }
        }

        return planList;
    }

7条回答 默认 最新

相关推荐 更多相似问题