请教一下算法问题

Question

有个int数组，里面有50个随机生成的数字，我想知道哪10个数字（必须是10个）加起来是等100的，一共几个组合

Answer 1

其实这个题貌似c(50,10)
不过应该没这么多，几个数字加起来大于100就BREAK了

Answer 2

我做了个,大家看看吧,用的全排列,排除了加起来超过100的组合.
本来还想在进位时最后一位遍历时左右移动的(因为在排好序的数中取下一个数变化不大,这样可以节约查找量)
我写出来运行了下,速度快了一倍多,不过一些特殊情况没处理到,大概漏了2W种组合(随机种子为1时,比例大概为百分之十几吧),不想浪费脑细胞完善了,这里那个结果不全的就不贴出来了,哪个有空的去处理下吧.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Random r = new Random(DateTime.Now.Millisecond);
            const int rNumber=50,upper=21,sNumber=10,total=100;   //随机数的数目,上限,选择的数的数量,选择的数的总和
            int[] randomNumber=new int[rNumber];    //随机数
            int i,j,sum=0,sub,count=0;
            for(i=0;i<rNumber;++i)
            {
                randomNumber[i]=r.Next(0,upper);       
            }
            DateTime d1 = DateTime.Now,d2;
            Array.Sort<int>(randomNumber);
            for (j = 0; j < rNumber; ++j)       //
            {
                Console.Write("{0},", randomNumber[j]);
            }
            Console.WriteLine("\b ");
            int[] selNumber = new int[sNumber - 1]; //保存临时组合的索引
            for (i = 0; i < sNumber - 1; ++i)
            {
                selNumber[i] = i;
            }
            for (i = 0; i < sNumber - 1; ++i)
            {
                sum += randomNumber[i];             //除最后一位的其它数字的总和
            }
            sub = total - sum;                  //除最后一位数字的组合与目标值的差
            while (sub > -1)
            {
                i=selNumber[sNumber-2];
                while (++i != rNumber)
                {
                    if (randomNumber[i] == sub)
                    {
                        count++;
                        //组合太多了,就不一一打出来了
                        //Console.WriteLine("{0},{1},{2},{3},{4},{5},{6},{7},{8},{9}", randomNumber[selNumber[0]], randomNumber[selNumber[1]], randomNumber[selNumber[2]], randomNumber[selNumber[3]], randomNumber[selNumber[4]], randomNumber[selNumber[5]], randomNumber[selNumber[6]], randomNumber[selNumber[7]], randomNumber[selNumber[8]], randomNumber[i]);
                    }
                    else if (randomNumber[i] > sub) break;
                }
                //最后一位选择数遍历结束,对组合进行进位;
                j=sNumber-2;
                while(++selNumber[j]==rNumber-sNumber+1+j)
                {
                    if (j == 0)
                    {
                        d2 = DateTime.Now;
                        Console.WriteLine("count={0},time={1}",count,d2-d1);
                        return;
                    }
                    j--; 
                }
                sub -= randomNumber[selNumber[j]] - randomNumber[selNumber[j]-1];
                while (++j < sNumber-1)
                {
                    selNumber[j] = selNumber[j - 1] + 1;
                    sub += randomNumber[rNumber-sNumber + j] - randomNumber[selNumber[j]];
                }
            }
            d2 = DateTime.Now;
            Console.WriteLine("count={0},time={1}", count, d2 - d1);
        }
    }
}结果:
0,0,0,0,1,1,2,2,3,4,4,4,4,5,5,5,6,7,7,8,8,8,9,10,10,11,11,13,13,14,14,15,15,15,1
6,16,16,17,17,17,17,17,18,18,19,19,20,20,20,20
count=145970,time=00:00:00.5781250

Answer 3

我上面的方法还是考虑漏了,现在改成下面的:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Random r = new Random(1);//DateTime.Now.Millisecond);
            const int rNumber=50,upper=21,sNumber=10,total=100;   //随机数的数目,上限,选择的数的数量,选择的数的总和
            int[] randomNumber=new int[rNumber];    //随机数
            int i,j,sum=0,sub,count=0;
            for(i=0;i<rNumber;++i)
            {
                randomNumber[i]=r.Next(0,upper);       
            }
            DateTime d1 = DateTime.Now,d2;
            Array.Sort<int>(randomNumber);
            for (j = 0; j < rNumber; ++j)       //
            {
                Console.Write("{0},", randomNumber[j]);
            }
            Console.WriteLine("\b ");
            int[] selNumber = new int[sNumber - 1]; //保存临时组合的索引
            for (i = 0; i < sNumber - 1; ++i)
            {
                selNumber[i] = i;
            }
            for (i = 0; i < sNumber - 1; ++i)
            {
                sum += randomNumber[i];             //除最后一位的其它数字的总和
            }
            sub = total - sum;                  //除最后一位数字的组合与目标值的差
            while (true)
            {
                if (sub > -1)
                {
                    i = selNumber[sNumber - 2];
                    while (++i != rNumber)
                    {
                        if (randomNumber[i] == sub)
                        {
                            count++;
                            //组合太多了,就不一一打出来了
                            //Console.WriteLine("{0},{1},{2},{3},{4},{5},{6},{7},{8},{9}", randomNumber[selNumber[0]], randomNumber[selNumber[1]], randomNumber[selNumber[2]], randomNumber[selNumber[3]], randomNumber[selNumber[4]], randomNumber[selNumber[5]], randomNumber[selNumber[6]], randomNumber[selNumber[7]], randomNumber[selNumber[8]], randomNumber[i]);
                        }
                        else if (randomNumber[i] > sub) break;
                    }
                }
                //最后一位选择数遍历结束,对组合进行进位;
                j=sNumber-2;
                while(++selNumber[j]==rNumber-sNumber+1+j)
                {
                    if (j == 0)
                    {
                        d2 = DateTime.Now;
                        Console.WriteLine("count={0},time={1}",count,d2-d1);
                        return;
                    }
                    j--; 
                }
                sub -= randomNumber[selNumber[j]] - randomNumber[selNumber[j]-1];
                while (++j < sNumber-1)
                {
                    selNumber[j] = selNumber[j - 1] + 1;
                    sub += randomNumber[rNumber-sNumber + j] - randomNumber[selNumber[j]];
                }
            }
            d2 = DateTime.Now;
            Console.WriteLine("count={0},time={1}", count, d2 - d1);
        }
    }
}结果:0,0,1,1,2,2,3,3,5,5,5,5,5,6,6,7,7,8,8,9,9,9,9,10,11,11,12,13,13,13,14,14,14,14,1
4,14,14,15,16,16,16,16,17,18,18,19,19,20,20,20
count=229374260,time=00:01:54.7031250
请按任意键继续. . .

Answer 4

上次JAVA EE板块有一个和你差不多的问题，我写了个算法，比较长，应该可以处理你的。只不过他是要把所有的组合求出来，而你只要包含10个元素的组合。。不过迭代计算，比较慢啊。针对你这个具体问题，应该可以改一下。。我试试看

Answer 5

我说的那个帖子的链接在下面：和你的类似 ，我的方法是针对他的情况的，用在你上面改有点麻烦，速度慢啊。
http://topic.csdn.net/u/20091027/21/dbf6fc7a-d21c-406f-8a17-4632fc54f715.html

Answer 6

我改成了把相同的数按同一组合算,
对前九位选择数进行全排列,因相同的数算同一组合,所以在进位时加了进位之后的数和原来数不同的判断
结果组合数降到10多万了,连把所有组合打印出来都只花了5S左右..
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Random r = new Random(DateTime.Now.Millisecond);
            const int rNumber=50,upper=21,sNumber=10,total=100;//随机数的数目,上限,选择的数的数量,选择的数的总和,平均数
            int[] randomNumber=new int[rNumber];    //随机数
            int i,j,sum=0,sub,count=0;
            for(i=0;i<rNumber;++i)
            {
                randomNumber[i]=r.Next(0,upper);       
            }
            DateTime d1 = DateTime.Now,d2;
            Array.Sort<int>(randomNumber);
            for (j = 0; j < rNumber; ++j)       //
            {
                Console.Write("{0},", randomNumber[j]);
            }
            Console.WriteLine("\b ");
            int[] selNumber = new int[sNumber - 1]; //保存临时组合的索引
            for (i = 0; i < sNumber - 1; ++i)
            {
                selNumber[i] = i;
            }
            for (i = 0; i < sNumber - 1; ++i)
            {
                sum += randomNumber[i];             //除最后一位的其它数字的总和
            }
            sub = total - sum;                  //除最后一位数字的组合与目标值的差
            while (true)
            {
                if (sub > -1&&sub<upper)
                {
                    i = selNumber[sNumber - 2];
                    while (++i != rNumber)
                    {
                        if (randomNumber[i] == sub)
                        {
                            count++;
                            //这里如果把组合打出来的话大概要花5s
                            //Console.WriteLine("{0},{1},{2},{3},{4},{5},{6},{7},{8},{9}", randomNumber[selNumber[0]], randomNumber[selNumber[1]], randomNumber[selNumber[2]], randomNumber[selNumber[3]], randomNumber[selNumber[4]], randomNumber[selNumber[5]], randomNumber[selNumber[6]], randomNumber[selNumber[7]], randomNumber[selNumber[8]], randomNumber[i]);
                            break;
                        }
                        else if (randomNumber[i] > sub) break;
                    }
                }
                j=sNumber-2;
                i = selNumber[j];
                do
                {
                    if (++selNumber[j] == rNumber - sNumber + 1 + j)
                    {
                        if (j == 0)
                        {
                            d2 = DateTime.Now;
                            Console.WriteLine("count={0},time={1}", count, d2 - d1);
                            return;
                        }
                        j--;
                        i = selNumber[j];
                    }
                    else if (randomNumber[selNumber[j]] != randomNumber[selNumber[j] - 1])
                    {
                        break;
                    }
                }while(true);
                sub -= randomNumber[selNumber[j]] - randomNumber[i];
                while (++j < sNumber-1)
                {
                    selNumber[j] = selNumber[j - 1] + 1;
                    sub += randomNumber[rNumber-sNumber + j] - randomNumber[selNumber[j]];
                }
            }
        }
    }
}结果:
0,1,2,3,3,3,3,3,4,4,4,4,4,5,5,5,6,6,6,7,7,8,8,9,9,10,10,10,11,12,13,14,14,14,14,
14,15,16,16,17,17,17,17,18,18,19,19,19,19,20
count=159043,time=00:00:00.3437500
请按任意键继续. . .