想的头痛,求高手

Question

有70个数(这70个数不是1到70的数哦),在70个数中找出哪几个数相加等于8000,2个或最多70个数相加也有可能,求程序的算法,哪位智商较高的朋友帮帮忙,谢谢了

Answer 1

比较简单的是穷举，
从1到70， 每个数都只有两种状态， 0代表这个解不包含这个数， 1代表这个解包含这个数，
然后计算所有标志为1的数的和， 得到一个结果与8000相比较
Count(int sum, int index)
{
    Count(sum, index + 1);
    Count(sum + number[index], index + 1);
}
另外应该可以用DP算法

Answer 2

笨算法，需要强悍计算机来完成  public class PermutationCombination
    {
        /// <summary>
        /// 交换两个变量
        /// </summary>
        /// <param name="a">变量1</param>
        /// <param name="b">变量2</param>
        public static void Swap(ref int a, ref int b)
        {
            
            int temp = a;
            a = b;
            b = temp;
        }
        /// <summary>
        /// 递归算法求数组的组合(私有成员)
        /// </summary>
        /// <param name="list">返回的范型</param>
        /// <param name="t">所求数组</param>
        /// <param name="n">辅助变量</param>
        /// <param name="m">辅助变量</param>
        /// <param name="b">辅助数组</param>
        /// <param name="M">辅助变量M</param>
        private static void GetCombination(ref List<int []> list, int [] t, int n, int m, int[] b, int M)
        {
            for (int i = n; i >= m; i--)
            {
                b[m - 1] = i - 1;
                if (m > 1)
                {
                    GetCombination(ref list, t, i - 1, m - 1, b, M);
                }
                else
                {
                    if (list == null)
                    {
                        list = new List<int []>();
                    }
                    int [] temp = new int [M];
                    for (int j = 0; j < b.Length; j++)
                    {
                        temp[j] = t[b[j]];
                    }
                    list.Add(temp);
                }
            }
        }
        /// <summary>
        /// 递归算法求排列(私有成员)
        /// </summary>
        /// <param name="list">返回的列表</param>
        /// <param name="t">所求数组</param>
        /// <param name="startIndex">起始标号</param>
        /// <param name="endIndex">结束标号</param>
        private static void GetPermutation(ref List<int []> list, int [] t, int startIndex, int endIndex)
        {
            if (startIndex == endIndex)
            {
                if (list == null)
                {
                    list = new List<int []>();
                }
                int [] temp = new int [t.Length];
                t.CopyTo(temp, 0);
                list.Add(temp);
            }
            else
            {
                for (int i = startIndex; i <= endIndex; i++)
                {
                    Swap(ref t[startIndex], ref t[i]);
                    GetPermutation(ref list, t, startIndex + 1, endIndex);
                    Swap(ref t[startIndex], ref t[i]);
                }
            }
        }
        /// <summary>
        /// 求从起始标号到结束标号的排列，其余元素不变
        /// </summary>
        /// <param name="t">所求数组</param>
        /// <param name="startIndex">起始标号</param>
        /// <param name="endIndex">结束标号</param>
        /// <returns>从起始标号到结束标号排列的范型</returns>
        public static List<int []> GetPermutation(int [] t, int startIndex, int endIndex)
        {
            if (startIndex < 0 || endIndex > t.Length - 1)
            {
                return null;
            }
            List<int []> list = new List<int []>();
            GetPermutation(ref list, t, startIndex, endIndex);
            return list;
        }
        /// <summary>
        /// 返回数组所有元素的全排列
        /// </summary>
        /// <param name="t">所求数组</param>
        /// <returns>全排列的范型</returns>
        public static List<int []> GetPermutation(int [] t)
        {
            return GetPermutation(t, 0, t.Length - 1);
        }
        /// <summary>
        /// 求数组中n个元素的排列
        /// </summary>
        /// <param name="t">所求数组</param>
        /// <param name="n">元素个数</param>
        /// <returns>数组中n个元素的排列</returns>
        public static List<int []> GetPermutation(int [] t, int n)
        {
            if (n > t.Length)
            {
                return null;
            }
            List<int []> list = new List<int []>();
            List<int []> c = GetCombination(t, n);
            for (int i = 0; i < c.Count; i++)
            {
                List<int []> l = new List<int []>();
                GetPermutation(ref l, c[i], 0, n - 1);
                list.AddRange(l);
            }
            return list;
        }
        /// <summary>
        /// 求数组中n个元素的组合
        /// </summary>
        /// <param name="t">所求数组</param>
        /// <param name="n">元素个数</param>
        /// <returns>数组中n个元素的组合的范型</returns>
        public static List<int []> GetCombination(int [] t, int n)
        {
            if (t.Length < n)
            {
                return null;
            }
            int[] temp = new int[n];
            List<int []> list = new List<int []>();
            GetCombination(ref list, t, t.Length, n, temp, n);
            return list;
        }
    }调用方法
 int[] arr = new int[70];
            for (int i = 0; i < arr.Length; i++)
            {
                arr[i] = i + 1;
            }
            //求组合
            List<int[]> lst_Combination = PermutationAndCombination<int>.GetCombination(arr, 35);
求出组合来后，楼主应该知道怎么做了吧，对每个数组要素求和，然后和8000做比较

Answer 3

/// <summary>
        /// 数据
        /// </summary>
        private int[] _number;
        /// <summary>
        /// 由于重复用到总和计算,这里用字典记录已计算过的值,减少重复计算
        /// </summary>
        private Dictionary<string, int> _numberSum;
        /// <summary>
        /// 由于重复用到索引找到,这里用字典记录已查找过的索引,减少重复查找
        /// </summary>
        private Dictionary<string, int> _searchIndex;        /// <summary>
        /// 开始执行计算
        /// beargo
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void button1_Click(object sender, EventArgs e)
        {
            _number = new int[] { 1, 3, 5, 7, 9, 10, 11, 12, 13, 15 };//设定数据.必须为按从小到大排序过的数据,这里你如果要70个数据再用随机数生成然后排序一下吧.
            _numberSum = new Dictionary<string, int>();
            _searchIndex = new Dictionary<string, int>();
            List<int[]> result = new List<int[]>();
            int sum = 25;//求匹配总和
            for (int i = 2; i < _number.Length; i++)
            {
                int[] newdata = new int[i];
                result.AddRange(beargo_GetData(newdata, 0, _number.Length, sum, 0));
            }
            MessageBox.Show(result.Count.ToString());//显示得到数据的总数..
        }        /// <summary>
        /// 获取N位(n>=2)不重复的匹配总值组合结果值
        /// </summary>
        /// <param name="data">当前数据</param>
        /// <param name="minnum">最小起始数值</param>
        /// <param name="maxnum">最大结束数值</param>
        /// <param name="sum">匹配组合总值</param>
        /// <param name="index">当前匹配位置索引</param>
        /// <returns>得到匹配的组合集合</returns>
        private List<int[]> beargo_GetData(int[] data, int minnum, int maxnum, int sum, int index)
        {
            List<int[]> result = new List<int[]>();
            int newindex = SearchNumberIndex(sum - GetNumberSum(_number.Length - data.Length + index, data.Length - index), true);
            minnum = newindex > minnum ? newindex : minnum;
            for (int i = minnum; i <= maxnum && sum - _number[i] >= GetNumberSum(i + 1, data.Length - index - 1); i++)
            {
                data[index] = _number[i];
                if (index == data.Length - 2)
                {
                    int endindex = SearchNumberIndex(sum - _number[i], false);
                    if (endindex > index)//当最后一位索引值大于前一位索引值,则匹配值成功,添加到列表中
                    {
                        data[index + 1] = _number[endindex];
                        result.Add((int[])data.Clone());
                    }
                }
                else
                {
                    result.AddRange(beargo_GetData(data, i + 1, maxnum, sum - _number[i], index + 1).ToArray());//开始计算一下位的数据。
                }
            }
            return result;
        }        /// <summary>
        /// 获取从第stratIndex共length位的总和
        /// </summary>
        /// <param name="stratIndex">开始索引</param>
        /// <param name="length">长度</param>
        /// <returns>总和</returns>
        private int GetNumberSum(int stratIndex, int length)
        {
            int result = 0;
            string key = string.Format("{0},{1}", stratIndex, length);
            if (_numberSum.ContainsKey(key))
            {
                result = _numberSum[key];
            }
            else
            {
                for (int i = stratIndex; i < stratIndex + length; i++)
                {
                    result += _number[i];
                }
                _numberSum[key] = result;
            }
            return result;
        }
        /// <summary>
        /// 利用二分查找法找到绝对或接近的匹配索引值
        /// </summary>
        /// <param name="value">匹配值</param>
        /// <param name="Approximation">如果没有绝对匹配的,是否取得最接近的索引值</param>
        /// <returns>索引</returns>
        private int SearchNumberIndex(int value, bool Approximation)
        {
            string key = string.Format("{0},{1}", value, Approximation);
            if (_searchIndex.ContainsKey(key))
            {
                return _searchIndex[key];
            }
            int low = 0, high = _number.Length - 1, middle = 0;
            while (low <= high)
            {
                middle = (low + high) / 2;
                if (value == _number[middle])
                {
                    _searchIndex[key] = middle;
                    return middle;
                }
                else if (value < _number[middle])
                {
                    high = middle - 1;
                }
                else
                {
                    low = middle + 1;
                }
            }
            if (!Approximation)//当不获取近似值时.又找不到数据.则索引号设置为-1
            { middle = -1; }
            _searchIndex[key] = middle;
            return middle;
        }
    }这个避免了所有数据的穷举.通过最大最小值的过滤.很大程度上优化了运算次数...试试!!

Answer 4

晕...有一小BUG.                    if (endindex > index)//当最后一位索引值大于前一位索引值,则匹配值成功,添加到列表中
替换成                    if (endindex > i)//当最后一位索引值大于前一位索引值,则匹配值成功,添加到列表中

Answer 5

/// <summary>
        /// 数据
        /// </summary>
        private List<int> _number;
       
        /// <summary>
        /// 开始执行计算
        /// beargo
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void button1_Click(object sender, EventArgs e)
        {
            _number = new List<int>();
            for (int i = 0; i < 70; i++)
            {
                _number.Add((i + 1) * 5);
            }
            List<int[]> result = new List<int[]>();
            int sum = 8000;//求匹配总和
            DateTime now = DateTime.Now;
            for (int i = 2; i < _number.Count; i++)
            {
                int[] newdata = new int[i];
                result.AddRange(beargo_GetData(newdata, 0, _number.Count - 1, sum, 0));
            }
            string value = "共找到:" + result.Count.ToString() + "个匹配值,耗时:" + DateTime.Now.Subtract(now).TotalSeconds.ToString() + "秒";
        }        /// <summary>
        /// 获取N位(n>=2)不重复的匹配总值组合结果值
        /// </summary>
        /// <param name="data">当前数据</param>
        /// <param name="minnum">最小起始数值</param>
        /// <param name="maxnum">最大结束数值</param>
        /// <param name="sum">匹配组合总值</param>
        /// <param name="index">当前匹配位置索引</param>
        /// <returns>得到匹配的组合集合</returns>
        private List<int[]> beargo_GetData(int[] data, int minnum, int maxnum, int sum, int index)
        {
            List<int[]> result = new List<int[]>();
            int startindex = _number.Count - data.Length + index;
            int numberSum = GetNumberSum(startindex, data.Length - index - 1);
            int newvalue = sum - numberSum;
            if (newvalue > _number[startindex - 1] || newvalue < _number[0])
            {
                return result;
            }
            int newindex = SearchNumberIndex(newvalue, true);
            minnum = newindex > minnum ? newindex : minnum;
            for (int i = minnum; i <= maxnum - data.Length + index && sum - _number[i] >= GetNumberSum(i + 1, data.Length - index - 1); i++)
            {
                data[index] = _number[i];
                if (index == data.Length - 2)
                {
                    int endindex = SearchNumberIndex(sum - _number[i], false);// _number.IndexOf(sum - _number[i]);感觉两速度差不多.
                    if (endindex > i)//当最后一位索引值大于前一位索引值,则匹配值成功,添加到列表中
                    {
                        data[index + 1] = _number[endindex];
                        result.Add((int[])data.Clone());
                    }
                }
                else
                {
                    result.AddRange(beargo_GetData(data, i + 1, maxnum, sum - _number[i], index + 1).ToArray());//开始计算一下位的数据。
                }
            }
            return result;
        }        /// <summary>
        /// 获取从第stratIndex共length位的总和
        /// </summary>
        /// <param name="stratIndex">开始索引</param>
        /// <param name="length">长度</param>
        /// <returns>总和</returns>
        private int GetNumberSum(int stratIndex, int length)
        {
            int result = 0;
            for (int i = stratIndex; i < stratIndex + length; i++)
            {
                result += _number[i];
            }
            return result;
        }
        /// <summary>
        /// 利用二分查找法找到绝对或接近的匹配索引值
        /// </summary>
        /// <param name="value">匹配值</param>
        /// <param name="Approximation">如果没有绝对匹配的,是否取得最接近的索引值</param>
        /// <returns>索引</returns>
        private int SearchNumberIndex(int value, bool Approximation)
        {
            int low = 0, high = _number.Count - 1, middle = 0;
            while (low <= high)
            {
                middle = (low + high) / 2;
                if (value == _number[middle])
                {
                    return middle;
                }
                else if (value < _number[middle])
                {
                    high = middle - 1;
                }
                else
                {
                    low = middle + 1;
                }
            }
            if (!Approximation)//当不获取近似值时.又找不到数据.则索引号设置为-1
            { middle = -1; }
            return middle;
        }重新修改过滤前面最小值判断.执行上面70个数求总和匹配8000得数据值:value共找到:14871个匹配值,耗时:4.421875秒

Answer 6

通过测试,用Dictionary索引还比重新计算慢...如果按前面使用Dictionary需要耗时5秒左右.多一秒钟...

Answer 7

 /// <summary>
        /// 数据
        /// </summary>
        private List<int> _number;        /// <summary>
        /// 开始执行计算
        /// beargo
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void button1_Click(object sender, EventArgs e)
        {
            _number = new List<int>();
            for (int i = 0; i < 70; i++)
            {
                _number.Add((i + 1) * 5);
            }
            List<int[]> result = new List<int[]>();
            int sum = 8000;//求匹配总和
            DateTime now = DateTime.Now;
            DataRequest = null;
            DataRequest += delegate(int[] data)
            {
                result.Add(data);
            };
            for (int i = 2; i < 31; i++)
            {
                int[] newdata = new int[i];
                beargo_GetData(newdata, 0, _number.Count - 1, sum, 0);
            }
            string value = "共找到:" + result.Count.ToString() + "个匹配值,耗时:" + DateTime.Now.Subtract(now).TotalSeconds.ToString() + "秒";
            MessageBox.Show(value);
        }        public delegate void DataRequestEventHandler(int[] data);
        public event DataRequestEventHandler DataRequest;
        /// <summary>
        /// 获取N位(n>=2)不重复的匹配总值组合结果值
        /// </summary>
        /// <param name="data">当前数据</param>
        /// <param name="minnum">最小起始数值</param>
        /// <param name="maxnum">最大结束数值</param>
        /// <param name="sum">匹配组合总值</param>
        /// <param name="index">当前匹配位置索引</param>
        /// <returns>得到匹配的组合集合</returns>
        private void beargo_GetData(int[] data, int minnum, int maxnum, int sum, int index)
        {
            int startindex = _number.Count - data.Length + index;
            int numberSum = GetNumberSum(startindex + 1, data.Length - index - 1);
            int newvalue = sum - numberSum;
            if (newvalue > _number[startindex - 1])
            {
                return;
            }
            int newindex = SearchNumberIndex(newvalue, true);
            minnum = newindex > minnum ? newindex : minnum;
            for (int i = minnum; i <= maxnum - data.Length + index && sum - _number[i] >= GetNumberSum(i + 1, data.Length - index - 1); i++)
            {
                data[index] = _number[i];
                if (index == data.Length - 2)
                {
                    int endindex = SearchNumberIndex(sum - _number[i], false);
                    if (endindex > i)//当最后一位索引值大于前一位索引值,则匹配值成功,添加到列表中
                    {
                        data[index + 1] = _number[endindex];
                        if (null != DataRequest)
                        {
                            DataRequest((int[])data.Clone());
                        }
                    }
                }
                else
                {
                    beargo_GetData(data, i + 1, maxnum, sum - _number[i], index + 1);
                }
            }
        }        /// <summary>
        /// 获取从第stratIndex共length位的总和
        /// </summary>
        /// <param name="stratIndex">开始索引</param>
        /// <param name="length">长度</param>
        /// <returns>总和</returns>
        private int GetNumberSum(int stratIndex, int length)
        {
            int result = 0;
            for (int i = stratIndex; i < stratIndex + length; i++)
            {
                result += _number[i];
            }
            return result;
        }
        /// <summary>
        /// 利用二分查找法找到绝对或接近的匹配索引值
        /// </summary>
        /// <param name="value">匹配值</param>
        /// <param name="Approximation">如果没有绝对匹配的,是否取得最接近的索引值</param>
        /// <returns>索引</returns>
        private int SearchNumberIndex(int value, bool Approximation)
        {
            int low = 0, high = _number.Count - 1, middle = 0;
            while (low <= high)
            {
                middle = (low + high) / 2;
                if (value == _number[middle])
                {
                    return middle;
                }
                else if (value < _number[middle])
                {
                    high = middle - 1;
                }
                else
                {
                    low = middle + 1;
                }
            }
            if (!Approximation)//当不获取近似值时.又找不到数据.则索引号设置为-1
            { middle = -1; }
            return middle;
        }
    }
前面版本有错漏..可匹配的数据至少有上亿个...这数据也太恐怖了...这里用事件通知来得到匹配的数据.计算30位的可匹配数据.
共找到:32818个匹配值,耗时:6.34375秒
31位有几百万可匹配数据,
32位有............
受不了了...除非你的数据很特殊,可匹配的总数不超过百万.要不然这么多可匹配数据算死你...
这个算法我只能优解到这种程度了(能力有限)...要是按求出组合再匹配8000这种算下去.应该要找我国的超级计算机去算了.....
各位有兴趣与建议的话,帮忙优化一下完善一下....

Answer 8

LZ是要求全解？还是任何一个解就可以？全解的话就搜索剪枝（有负数么？），求一个解的话就用DP（得是整数，否则也不好办），就像楼上说的是个背包问题