110,580
社区成员
发帖
与我相关
我的任务
分享想的头痛,求高手
有70个数(这70个数不是1到70的数哦),在70个数中找出哪几个数相加等于8000,2个或最多70个数相加也有可能,求程序的算法,哪位智商较高的朋友帮帮忙,谢谢了
...全文
请发表友善的回复…
发表回复
mrsupersky 2011-08-08
- 打赏
- 举报
全解。。。
wubudang 2010-11-05
- 打赏
- 举报
[Quote=引用 25 楼 litaoye 的回复:]
LZ是要求全解？还是任何一个解就可以？全解的话就搜索剪枝（有负数么？），求一个解的话就用DP（得是整数，否则也不好办），就像楼上说的是个背包问题
[/Quote]
我想负数、无理数、小数等这些都不应该算在其中，不然怎么搞。
LZ是要求全解？还是任何一个解就可以？全解的话就搜索剪枝（有负数么？），求一个解的话就用DP（得是整数，否则也不好办），就像楼上说的是个背包问题
[/Quote]
我想负数、无理数、小数等这些都不应该算在其中，不然怎么搞。
beargo 2010-11-05
- 打赏
- 举报
楼主还是把这70个数放出来看看吧...穷举组合再跟8000比较是不实际的..70个数的31位组合数据量就大的惊人..咱普通计算机是否能穷举完是个问题啊!~!只要楼主的70个数据实际能组合出8000的数据量不多时,我提供的代码还是能比较快的计算过滤出来的.
beargo 2010-11-04
- 打赏
- 举报
通过测试,用Dictionary索引还比重新计算慢...如果按前面使用Dictionary需要耗时5秒左右.多一秒钟...
beargo 2010-11-04
- 打赏
- 举报
/// <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秒
jetlee1986 2010-11-04
- 打赏
- 举报
[Quote=引用 7 楼 loveifa 的回复:]
70 不是一个很大的数字。。
可以穷举
[/Quote]
话不能这么说。背包穷举的时间复杂度太大了
70 不是一个很大的数字。。
可以穷举
[/Quote]
话不能这么说。背包穷举的时间复杂度太大了
绿色夹克衫 2010-11-04
- 打赏
- 举报
LZ是要求全解？还是任何一个解就可以？全解的话就搜索剪枝（有负数么？），求一个解的话就用DP（得是整数，否则也不好办），就像楼上说的是个背包问题
peng2739956 2010-11-04
- 打赏
- 举报
肯定用到穷举啊 这题目给你的时候 你就得想到用穷举啊 完了之后 用索引
liutao8984908 2010-11-04
- 打赏
- 举报
楼上的都好强！！
beargo 2010-11-04
- 打赏
- 举报
不能穷举...
wubudang 2010-11-04
- 打赏
- 举报
[Quote=引用 16 楼 beargo 的回复:]
引用 15 楼 wubudang 的回复:
8000可以分成：7999+1，7998+1+1，7998+2。。。太多了。好像有个算法的，忘记了。我智商比较低的。
但要看清楚题目...
[/Quote]
把8000拆分的结果再跟70个数相比较，只是一个不知道好不好的方法。
引用 15 楼 wubudang 的回复:
8000可以分成：7999+1，7998+1+1，7998+2。。。太多了。好像有个算法的，忘记了。我智商比较低的。
但要看清楚题目...
[/Quote]
把8000拆分的结果再跟70个数相比较，只是一个不知道好不好的方法。
Relict 2010-11-04
- 打赏
- 举报
学习了++
穷举？？、
这运算量没的说
穷举？？、
这运算量没的说
a5855523 2010-11-04
- 打赏
- 举报
支持！！！！！！
beargo 2010-11-04
- 打赏
- 举报
[Quote=引用 15 楼 wubudang 的回复:]
8000可以分成：7999+1，7998+1+1，7998+2。。。太多了。好像有个算法的，忘记了。我智商比较低的。
[/Quote]
但要看清楚题目...
8000可以分成：7999+1，7998+1+1，7998+2。。。太多了。好像有个算法的，忘记了。我智商比较低的。
[/Quote]
但要看清楚题目...
wubudang 2010-11-04
- 打赏
- 举报
8000可以分成：7999+1，7998+1+1，7998+2。。。太多了。好像有个算法的，忘记了。我智商比较低的。
beargo 2010-11-04
- 打赏
- 举报
/// <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这种算下去.应该要找我国的超级计算机去算了.....
各位有兴趣与建议的话,帮忙优化一下完善一下....
xiehuanxie 2010-11-03
- 打赏
- 举报
[Quote=引用 8 楼 lishenghu365 的回复:]
引用 7 楼 loveifa 的回复:
70 不是一个很大的数字。。
可以穷举
自己测试一下就知道是不是大数字了。。。
[/Quote]
2的70次方， 想想。。。
引用 7 楼 loveifa 的回复:
70 不是一个很大的数字。。
可以穷举
自己测试一下就知道是不是大数字了。。。
[/Quote]
2的70次方， 想想。。。
beargo 2010-11-03
- 打赏
- 举报
晕...有一小BUG.
if (endindex > index)//当最后一位索引值大于前一位索引值,则匹配值成功,添加到列表中
替换成
if (endindex > i)//当最后一位索引值大于前一位索引值,则匹配值成功,添加到列表中
if (endindex > index)//当最后一位索引值大于前一位索引值,则匹配值成功,添加到列表中
替换成
if (endindex > i)//当最后一位索引值大于前一位索引值,则匹配值成功,添加到列表中
beargo 2010-11-03
- 打赏
- 举报
/// <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;
}
}
这个避免了所有数据的穷举.通过最大最小值的过滤.很大程度上优化了运算次数...试试!!
李先生2017 2010-11-03
- 打赏
- 举报
[Quote=引用 7 楼 loveifa 的回复:]
70 不是一个很大的数字。。
可以穷举
[/Quote]
自己测试一下就知道是不是大数字了。。。
70 不是一个很大的数字。。
可以穷举
[/Quote]
自己测试一下就知道是不是大数字了。。。
加载更多回复（7）
