C#程序，求算法
我有一个 List<int> ary ，里面的数字可以任意多而且任意大。需求是这样的：
从外边接收一个数字（例如100），我要从数组里去找出哪几个相加之后正好是100（可能是两个数相加，也可能是多个数相加），相加的次数以少为优，如果有匹配的，把那几个数的下标保存起来。
这个程序应该怎样写呢？？？
--------------------编程问答-------------------- --------------------编程问答-------------------- 恩，很不简单的算法！ --------------------编程问答--------------------
--------------------编程问答--------------------
动规吧
--------------------编程问答--------------------
非常滴不简单...
--------------------编程问答--------------------
复杂……懒的弄
--------------------编程问答--------------------
数组如果是常用的话,则考虑象建立索引文件的原理,增加一维
--------------------编程问答--------------------
考虑了一下，我这样想的，最少就是两个数字，那么就两个开始计算，不行就三个，依次增加数字个数直到找到首先排除掉比100大的数字，那些肯定不行
两个数字的情况：
对剩下的数字进行从大到小排序，开始遍历，两个数字和等于100的话那么大的那个肯定大于100/2，遍历所有的大于100/2的数字就行了，对第一个数字P1，求100-P1,如果剩余的数字里存在100-P1，那么就是它了，如果没有继续遍历直到100/2
三个数字的情况：
对剩下的数字进行从大到小排序，开始遍历，三个数字和等于100的话那么大的那个肯定大于100/3，遍历所有的大于100/3的数字就行了，对第一个数字P1，求100-P1,然后调用两个数字的情况，求剩下的数字里边和为100-P1的数字
依次类推
--------------------编程问答-------------------- 只需要写1行Linq代码就行了。
但是写了你可能也看不懂。如果还停留在抄代码的阶段，那么还是自己花点时间搞出来吧。 --------------------编程问答-------------------- --------------------编程问答--------------------
需少应该是1个数字。
如果要求合计为x的结果得到的所有可能的组合的列表，那么任选一个数字a，只要得到合计为（x-a）的所有可能的组合的列表，然后把a加入这个列表中的每一项。同时要组合那些1个数字等于x的所有结果。 --------------------编程问答-------------------- 挺复杂的，11楼的说的不错！可以以8楼的为基础好好想想。 --------------------编程问答-------------------- 随便写了一下，不一定保证完全正确，希望看懂思路就好：
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApplication1
{
class Program
{
public static List<int> Nums = new List<int> { 1, 2, 10, 23, 11, 45, 8, 89, 42, 63 };
public static IEnumerable<IEnumerable<int>> Solve(IEnumerable<int> indexes, int goal)
{
return (from x in indexes where Nums[x] == goal select new List<int> { x }).Concat(
from x in indexes
from s in Solve(indexes.Where(i => i > x && x <= goal - Nums[x]), goal - Nums[x])
select s.Union(new int[] { x }));
}
public static void Main()
{
Console.WriteLine("打印所有元素的下标，每一行为一个解答：");
var res = new List<List<int>>();
foreach (var solve in Solve(Enumerable.Range(0, Nums.Count), 100))
{
var lst = solve.ToList();
res.Add(lst);
foreach (var x in lst)
Console.Write("{0} ", x);
Console.WriteLine();
}
var cnt = res.Min(s => s.Count());
Console.WriteLine("最短的是{0}数字的组合。", cnt);
foreach (var solve in res.Where(s => s.Count() == cnt))
{
foreach (var x in solve)
Console.Write("{0} ", x);
Console.WriteLine();
}
Console.ReadKey();
}
}
}
大量时间花在打印上了，其实算法只是简单的一个solve方法而已。 --------------------编程问答-------------------- 大量时间花在打印上了 --> 大量代码花在打印上了 --------------------编程问答-------------------- 啊哈，又看了一下，算法中写错了一点：
public static IEnumerable<IEnumerable<int>> Solve(IEnumerable<int> indexes, int goal)
{
return (from x in indexes where Nums[x] == goal select new List<int> { x }).Concat(
from x in indexes
from s in Solve(indexes.Where(i => i > x && Nums[i] <= goal - Nums[x]), goal - Nums[x])
select s.Union(new int[] { x }));
}
读一下算法就知道了。 --------------------编程问答-------------------- var result =from a in lst
from b in lst
from c in lst where a+b+c=100
select new { A = a, B = b, C = c };
索引Select((a, index) => new { a, index }) --------------------编程问答-------------------- 从实用的角度，不仅仅是看重“算法”问题，而且会看重Linq的延迟计算功能（即自动编译为迭代器算法功能）。
如果你先把所有可能的组合求出来，然后才开始打印，那么会等待很长时间。这样用户就会对这个程序不耐烦。所以
foreach (var solve in Solve(Enumerable.Range(0, Nums.Count), 100))这一句，是每当找到一个组合于是就打印一次求解中间进度，可以给用户及时的反馈。
类似地，当你使用 DirectoryInfo 类对象来遍历大目录下的文件时，使用 EnumerateFiles 而不是使用 GetFiles 方法。这些都是实用性地去编程，需要了解的知识。 --------------------编程问答-------------------- 相加的次数以少为优
深度优先+贪婪回溯即可 --------------------编程问答-------------------- 原来linq还可以这样用，长见识了。 --------------------编程问答-------------------- 嗯，看了一下#8的想法。不去查找所有结果，而是试探2个元素的组合、不成就试探3个.....，也是更快的。
重写这个程序：
using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApplication1
{
class Program
{
public static List<int> Nums = new List<int> { 1, 2, 10, 23, 11, 45, 8, 89, 42, 63 };
public static IEnumerable<IEnumerable<int>> Solve(IEnumerable<int> indexes, int goal, int 要求元素个数)
{
if (要求元素个数 == 1)
return from x in indexes
where Nums[x] == goal
select new int[] { x };
else
return from x in indexes
from s in Solve(indexes.Where(i => i > x && Nums[i] <= goal - Nums[x]), goal - Nums[x], 要求元素个数 - 1)
select s.Union(new int[] { x });
}
public static void Main()
{
for (var i = 2; i <= Nums.Count; i++)
{
var res = Solve(Enumerable.Range(0, Nums.Count), 100, 2).FirstOrDefault().ToList();
if (res != null)
{
Console.WriteLine("打印所有元素的下标，只打印2个元素的组合的第一个解答：");
foreach (var x in res)
Console.Write("{0} ", x);
break;
}
}
Console.ReadKey();
}
}
}
这个新的Solve方法就是新的“算法”。
--------------------编程问答-------------------- 呵呵，错把i写成2了！
using System;--------------------编程问答--------------------
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApplication1
{
class Program
{
public static List<int> Nums = new List<int> { 1, 2, 10, 23, 11, 45, 8, 89, 42, 63 };
public static IEnumerable<IEnumerable<int>> Solve(IEnumerable<int> indexes, int goal, int 要求元素个数)
{
if (要求元素个数 == 1)
return from x in indexes
where Nums[x] == goal
select new int[] { x };
else
return from x in indexes
from s in Solve(indexes.Where(i => i > x && Nums[i] <= goal - Nums[x]), goal - Nums[x], 要求元素个数 - 1)
select s.Union(new int[] { x });
}
public static void Main()
{
for (var i = 2; i <= Nums.Count; i++)
{
var res = Solve(Enumerable.Range(0, Nums.Count), 100, i).FirstOrDefault().ToList();
if (res != null)
{
Console.WriteLine("打印所有元素的下标，只打印{0}个元素的组合的第一个解答：", i);
foreach (var x in res)
Console.Write("{0} ", x);
break;
}
}
Console.ReadKey();
}
}
}
linq本来“就应该这样用”！
你的大多数程序，其实就是要把原来成百行甚至上千行计算代码，只用一条清晰的Linq代码来集中写出算法逻辑。然后跟上一个输出显示语句。 --------------------编程问答--------------------
你试过？数据多点估计没个10年8年跑不出来。
你这个例子恰好说明了滥用linq的危害。 --------------------编程问答-------------------- --------------------编程问答-------------------- 嗯，多写了一个 ToList()，应该删除。 --------------------编程问答--------------------
--------------------编程问答--------------------
一开始想到了陈景润（好吧差太远了）
--------------------编程问答--------------------
这个貌似以前有出现过类似的..
/// <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;
}
}
http://topic.csdn.net/u/20101103/14/3301faea-2bf7-43a1-9f6c-e1d7b882de45.html
--------------------编程问答--------------------
是不是只要“用”就算是“滥用”？
那么什么叫做滥用？ --------------------编程问答-------------------- 写个实际结果数据出来来说明什么是“滥用”嘛！
比如我根据#8楼的想法，于是修改了一个程序出来。这只能说明关键的问题在于算法，而不是用不用Linq。我反而倒是很想用一个实例，知道这里怎么就算是滥用Linq了呢？ --------------------编程问答-------------------- linq只会回溯，而且是N^N级别的回溯
随便加个剪枝都能提高几百倍效率
要是再做个PD，估计可以把linq跑10年的东西在一个小时内跑出来
补充：.NET技术 , C#
