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

求一组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条回答 默认 最新

  • threenewbee 2018-04-26 03:43
    关注
     using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    
    namespace ConsoleApplication1
    {
        class Program
        {
            static void Main(string[] args)
            {
                int[] arr = { 15, 25, 30, 35, 45, 50, 55, 70, 80, 100 };
                int sum = 150;
                foreach (var item in Solve(arr, sum))
                {
                    Console.WriteLine(string.Join(", ", item.Skip(1)));
                }
            }
            static IEnumerable<IEnumerable<int>> Solve(int[] arr, int sum, IEnumerable<int> feed = null)
            {
                if (feed == null) feed = new List<int>() { 0 };
                if (feed.Sum() == sum) yield return feed;
                foreach (int n in arr.Where(x => x + feed.Sum() <= sum))
                {
                    foreach (var item in Solve(arr, sum, feed.Concat(new int[] { n }))) yield return item;
                }
            }
        }
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(6条)

报告相同问题?