想的头痛,求高手
有70个数(这70个数不是1到70的数哦),在70个数中找出哪几个数相加等于8000,2个或最多70个数相加也有可能,求程序的算法,哪位智商较高的朋友帮帮忙,谢谢了 --------------------编程问答-------------------- 背包问题? --------------------编程问答-------------------- 朋友们别太冷漠呀 --------------------编程问答-------------------- 比较简单的是穷举，从1到70， 每个数都只有两种状态， 0代表这个解不包含这个数， 1代表这个解包含这个数，
然后计算所有标志为1的数的和， 得到一个结果与8000相比较
Count(int sum, int index)
{
Count(sum, index + 1);
Count(sum + number[index], index + 1);
}
另外应该可以用DP算法 --------------------编程问答-------------------- 笨算法，需要强悍计算机来完成
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做比较 --------------------编程问答-------------------- 先谢谢了,测试看看 --------------------编程问答-------------------- 调用时要在外层做一个循环，1到70个数都有可能吧，所以很担心楼主的机器啊！！！！ --------------------编程问答-------------------- 70 不是一个很大的数字。。
可以穷举 --------------------编程问答--------------------
自己测试一下就知道是不是大数字了。。。 --------------------编程问答--------------------
/// <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;
}
}
这个避免了所有数据的穷举.通过最大最小值的过滤.很大程度上优化了运算次数...试试!! --------------------编程问答-------------------- 晕...有一小BUG.
if (endindex > index)//当最后一位索引值大于前一位索引值,则匹配值成功,添加到列表中
替换成
if (endindex > i)//当最后一位索引值大于前一位索引值,则匹配值成功,添加到列表中
--------------------编程问答--------------------
2的70次方， 想想。。。
--------------------编程问答--------------------
/// <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秒 --------------------编程问答-------------------- 通过测试,用Dictionary索引还比重新计算慢...如果按前面使用Dictionary需要耗时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;
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这种算下去.应该要找我国的超级计算机去算了.....
各位有兴趣与建议的话,帮忙优化一下完善一下.... --------------------编程问答-------------------- 8000可以分成：7999+1，7998+1+1，7998+2。。。太多了。好像有个算法的，忘记了。我智商比较低的。 --------------------编程问答--------------------
但要看清楚题目... --------------------编程问答-------------------- 支持！！！！！！ --------------------编程问答-------------------- 学习了++
穷举？？、
这运算量没的说 --------------------编程问答--------------------
把8000拆分的结果再跟70个数相比较，只是一个不知道好不好的方法。 --------------------编程问答-------------------- 不能穷举... --------------------编程问答-------------------- 楼上的都好强！！ --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答-------------------- 肯定用到穷举啊 这题目给你的时候 你就得想到用穷举啊 完了之后 用索引 --------------------编程问答-------------------- LZ是要求全解？还是任何一个解就可以？全解的话就搜索剪枝（有负数么？），求一个解的话就用DP（得是整数，否则也不好办），就像楼上说的是个背包问题 --------------------编程问答--------------------
话不能这么说。背包穷举的时间复杂度太大了 --------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答-------------------- 楼主还是把这70个数放出来看看吧...穷举组合再跟8000比较是不实际的..70个数的31位组合数据量就大的惊人..咱普通计算机是否能穷举完是个问题啊!~!只要楼主的70个数据实际能组合出8000的数据量不多时,我提供的代码还是能比较快的计算过滤出来的. --------------------编程问答--------------------
我想负数、无理数、小数等这些都不应该算在其中，不然怎么搞。 --------------------编程问答-------------------- --------------------编程问答-------------------- 全解。。。
补充：.NET技术 , C#
