数组求和（一个数组有N个数求其中几个数加起来接近一个数）

两个数的,下面的代码是个例子,两个以上的你要递归到2个做,也是可以实现的            int[] iArray = new int[] { 14, 3, 7, 8, 9, 5, 12, 2, 13, 1, 6, 4 };
            List<int> iList = new List<int>(iArray);
            iList.Sort();            for (int sum = 15; sum > 10;sum-- )
            {
                for (int index = 0; index < iList.Count; index++)
                {
                    int val = iList[index];
                    int remain = sum - val;
                    int remainInex = iList.IndexOf(remain);
                    if (remainInex > index)
                    {
                        Console.WriteLine(string.Format("{0}+{1}", val, remain));
                    }
                }
            }

private void button1_Click(object sender, System.EventArgs e)
{
int[] array=new int[] { 14, 3, 7, 8, 9, 5, 12, 2, 13, 1, 6, 4 };
int sum=15;
this.textBox1.Text=GetNearSum(array,sum); } private string GetNearSum(int[] numbers,int sum)
{
int count=numbers.Length;
int tempSum=int.MinValue;
string result=string.Empty;
for(int i=0;i<count;i++)
{
for(int j=i+1;j<count;j++)
{
int temp=numbers[i]+numbers[j];
if(temp==tempSum)
{
result+=" "+numbers[i]+"+"+numbers[j];
}
else if(temp>tempSum&&temp<=sum)
{
result=numbers[i]+"+"+numbers[j];
tempSum=temp;
}
}
}
return result;
}2个数，不排序，输出结果是：14+1 3+12 7+8 9+6 2+13

int[] iArray = new int[] { 14, 3, 7, 8, 9, 5, 12, 2, 13, 1, 6, 4 };
            List<int> iList = new List<int>(iArray);
            iList.Sort();            for (int sum = 15; sum > 10;sum-- )
            {
                for (int index = 0; index < iList.Count; index++)
                {
                    int val = iList[index];
                    int remain = sum - val;
                    int remainInex = iList.IndexOf(remain);
                    if (remainInex > index)
                    {
                        Console.WriteLine(string.Format("{0}+{1}", val, remain));
                    }
                }
            }

谈谈我的思路,要用到递归
先写一个函数F(M,N),从任意M个数中抽取N个数
在循环调用
F(M,1),F(M,2)..........
从而得到从任意M个数中抽取任意X个数(X<=M)
然后计算他们的和

        private   List<string> SelectFromArr(int[] Arr, int Num,int Start)
        {
            List<string> l=new List<string>();
            if (Num==1)
            {
                for (int i=Start ;i<Arr.Length ;i++)
                {
                    l.Add(Arr[i].ToString());
                }
                return l;
            }
            else
            {
                for (int i = Start; i < Arr.Length - 1; i++)
                {
                    foreach (string s in SelectFromArr(Arr, Num - 1, i + 1))
                    {
                        l.Add(Arr[i].ToString() + "," + s);
                    }
                }
                return l;
            }
        }        private List<string> SelectXFromArr(int[] Arr, int Num, int Start)
        {
            List<string> l = new List<string>();
            for (int i = 1; i <= Arr.Length ; i++)
            {
                foreach (string s in SelectFromArr(Arr, i, 0))
                {
                    l.Add(s);
                }
            }
            return l;
        }
        private void Form1_Load(object sender, EventArgs e)
        {
            int[] arr={14,3,7,8,9,5,12,2,13,1,2,6,4};
            foreach (string s in SelectXFromArr(arr, 3, 0))
            {
                if (SumFromStr(s) == 15)
                {
                    Console.WriteLine(s);
                }
            }

        }
        private int SumFromStr(string s)
        {
            int r = 0;
            foreach (string s1 in s.Split(','))
            {
                r += Convert.ToInt32(s1);
            }
            return r;
        }

数组求和（一个数组有N个数求其中几个数加起来接近一个数） is a knapsack problem.
It can be solved in O(WN) using dynamic programming, where N is the array count and W is the target number.You might google for "knapsack problem" and try the solution yourself.
I do have some code in case you have difficulties doing it.

写了一个，你的数据测了，没有问题，没有测试大量数据，你自己看看吧，支持多个数的。using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApp
{
    public class HeapingStore
    {
        double m_HeapSize = 0;
        List<double> m_Items;        public HeapingStore(double heapSize, List<double> items)
        {
            m_HeapSize = heapSize;
            m_Items = items;
        }        public List< List<double> > NeatenHeap()
        {
            List<List<double>> result = new List<List<double>>();
            m_Items.Sort(new Comparison<double>(delegate(double d1, double d2)
                {
                    return Comparer<double>.Default.Compare(d1, d2) * -1;
                }
            ));            List<double> group;            while(m_Items.Count>0)
            {
                group = new List<double>();
                group.Add(m_Items[0]);
                double delta = m_HeapSize - m_Items[0];

                if (delta > 0&&m_Items.Count>2)
                {
                    List<double> validDeltas = new List<double>();
                    for (int i = 1; i < m_Items.Count; i++)
                    {
                        if (m_Items[i] <= delta)
                        {
                            validDeltas.Add(m_Items[i]);
                        }
                    }
                    group.AddRange(GetMostApproximate(delta, validDeltas));
                }                foreach (double d in group)
                {
                    for (int i = 0; i < m_Items.Count; i++)
                    {
                        if (m_Items[i] == d)
                        {
                            m_Items.RemoveAt(i);
                            break;
                        }
                    }
                }                result.Add(group);
            }            return result;
        }        private List<double> GetMostApproximate(double wanted, List<double> validProvides)
        {
            List<double> result = new List<double>();
            validProvides.Sort(new Comparison<double>(delegate(double d1, double d2)
            {
                return Comparer<double>.Default.Compare(d1, d2) * -1;
            }
            ));
            result.Add(validProvides[0]);
            double delta = wanted - validProvides[0];
            validProvides.RemoveAt(0);            if (delta.Equals(0)==false)
            {
                List<double> validDeltas = validProvides.FindAll(new Predicate<double>(delegate(double d)
                {
                    return d <= delta;
                }
                ));
                if (validDeltas != null && validDeltas.Count > 0)
                {
                    result.AddRange(GetMostApproximate(delta, validDeltas));
                }
            }            return result;
        }
    }
}using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            List<double> input = new List<double>();
            //14，3,7,8,9,5,12,2,13,1,2,6,4
            input.Add(14);
            input.Add(3);
            input.Add(7);
            input.Add(8);
            input.Add(9);
            input.Add(5);
            input.Add(12);
            input.Add(2);
            input.Add(13);
            input.Add(1);
            input.Add(2);
            input.Add(6);
            input.Add(4);            HeapingStore hs = new HeapingStore(15, input);
           List<List<double>> result= hs.NeatenHeap();            foreach(List<double> group in result)
            {
                foreach(double d in group)
                {
                    Console.Write("{0},", d);
                }
                Console.WriteLine();
            }            Console.Read();
        }
    }
}

namespace WindowsApplication11
{
    public partial class Form1 : Form
    {
        String Result = String.Empty;
        int Num = 10; // 15 输出太多改10了        public Form1()
        {
            InitializeComponent();            List<int> A = new List<int>();
            String TempResult = String.Empty;
            int TempCal = 0;
            A.Add(14);
            A.Add(3);
            A.Add(7);
            A.Add(8);
            A.Add(9);
            A.Add(5);
            A.Add(12);
            A.Add(2); // 你有个2重复了，我去掉了一个
            A.Add(13);
            A.Add(1);
            A.Add(6);
            A.Add(4);
            for (int i = Num; i > 0; i--)
            {
                GetIt(i, A, TempResult, TempCal);
                Result = Result.Replace(" ", "=" + i.ToString() + ",");
            }
            Result = Result.Replace(".", "+");
            Result = Result.Replace("+=", "=");
            if (Result.Length > 0)
                Result = Result.Remove(Result.Length - 1);
            MessageBox.Show(Result);
        }
        void GetIt(int Num, List<int> A, String TempResult, int TempCal)
        {
            for (int i = 0; i < A.Count; i++)
            {
                String Temp1 = TempResult;
                int Temp2 = TempCal;
                TempResult += A[i].ToString() + ".";
                TempCal += Convert.ToInt32(A[i]);
                if (TempCal == Num)
                {
                    // 这里你自己加上去掉重复的代码                    if (TempResult.IndexOf('.') != TempResult.LastIndexOf('.'))
                        Result += TempResult + " ";
                }
                else if (TempCal < 15)
                {
                    List<int> B = new List<int>();
                    foreach (int X in A)
                        B.Add(X);
                    B.RemoveAt(i);
                    GetIt(Num, B, TempResult, TempCal);
                }
                TempResult = Temp1;
                TempCal = Temp2;
            }
        }
    }
}你自己再去判断一下重复的情况不要加进结果就可以了
比如10: 1+9 和 9+1 是一样的输出结果（10）（没去掉重复）：
3+7=10,3+5+2=10,3+2+5=10,3+2+1+4=10,3+2+4+1=10,3+1+2+4=10,3+1+6=10,3+1+4+2=10,3+6+1=10,3+4+2+1=10,3+4+1+2=10,7+3=10,7+2+1=10,7+1+2=10,8+2=10,9+1=10,5+3+2=10,5+2+3=10,5+1+4=10,5+4+1=10,2+3+5=10,2+3+1+4=10,2+3+4+1=10,2+7+1=10,2+8=10,2+5+3=10,2+1+3+4=10,2+1+7=10,2+1+4+3=10,2+4+3+1=10,2+4+1+3=10,1+3+2+4=10,1+3+6=10,1+3+4+2=10,1+7+2=10,1+9=10,1+5+4=10,1+2+3+4=10,1+2+7=10,1+2+4+3=10,1+6+3=10,1+4+3+2=10,1+4+5=10,1+4+2+3=10,6+3+1=10,6+1+3=10,6+4=10,4+3+2+1=10,4+3+1+2=10,4+5+1=10,4+2+3+1=10,4+2+1+3=10,4+1+3+2=10,4+1+5=10,4+1+2+3=10,4+6=10,3+5+1=9,3+2+4=9,3+1+5=9,3+6=9,3+4+2=9,7+2=9,8+1=9,5+3+1=9,5+1+3=9,5+4=9,2+3+4=9,2+7=9,2+1+6=9,2+6+1=9,2+4+3=9,1+3+5=9,1+8=9,1+5+3=9,1+2+6=9,1+6+2=9,6+3=9,6+2+1=9,6+1+2=9,4+3+2=9,4+5=9,4+2+3=9,3+5=8,3+1+4=8,3+4+1=8,7+1=8,5+3=8,5+2+1=8,5+1+2=8,2+5+1=8,2+1+5=8,2+6=8,1+3+4=8,1+7=8,1+5+2=8,1+2+5=8,1+4+3=8,6+2=8,4+3+1=8,4+1+3=8,3+4=7,5+2=7,2+5=7,2+1+4=7,2+4+1=7,1+2+4=7,1+6=7,1+4+2=7,6+1=7,4+3=7,4+2+1=7,4+1+2=7,3+2+1=6,3+1+2=6,5+1=6,2+3+1=6,2+1+3=6,2+4=6,1+3+2=6,1+5=6,1+2+3=6,4+2=6,3+2=5,2+3=5,1+4=5,4+1=5,3+1=4,1+3=4,2+1=3,1+2=3

随便写了一个，但是写的不是很好，我有空再改改。
            int[] array = new int[] { 14, 3, 7, 8, 9, 5, 12, 2, 13, 1, 2, 6, 4 };
            Array.Sort(array);
            List<List<int>> result = new List<List<int>>();
            int lastNum = 0;
            for (int i = array.Length - 1; i >= lastNum; i--)
            {
                int tmp = array[i] ;
                List<int> iList = new List<int>();
                iList.Add(tmp);
                for (int j = lastNum; j < lastNum + 1; j++)
                {
                    tmp = tmp + array[lastNum];
                    iList.Add(array[lastNum]);
                    if (tmp > 15)
                    {
                        iList.Remove(array[lastNum]);
                        break;
                    }
                    else
                    {
                        lastNum++;
                    }
                }
                result.Add(iList);
            }

满足LZ提出的需求,每个数只使用一次,找出所有小于等于目标值的集合.
    class Program
    {
        static void Main(string[] args)
        {
            Get(15); //期望的和
        }        static void Get(int num)
        {
            Dictionary<int, ArrayList> result = new Dictionary<int, ArrayList>();
            int[] nums = { 14, 3, 7, 8, 9, 5, 12, 2, 13, 1, 2, 6, 4 };
            Array.Sort(nums, new Comparison<int>(function));
            ArrayList array = new ArrayList(nums);

            int count = 0;
            for (int i = 0; i < array.Count; i++)
            {
                ArrayList resultList = new ArrayList();
                resultList.Add(array[i]);
                array.Remove(array[i]);
                for (int j = 0; j < array.Count; j++)
                {
                    if ((int)array[j] <= num - GetSum(resultList))
                    {
                        resultList.Add(array[j]);
                        array.Remove(array[j]);
                    }
                }
                result.Add(count++, resultList);
                i = 0;
            }

            Console.WriteLine("原数据:");
            for (int k = 0; k < nums.Length; k++)
            {
                Console.Write(nums[k].ToString() + " ");
            }
            Console.WriteLine();
            Console.WriteLine(String.Format("和为:{0}",num.ToString()));
            Console.WriteLine("结果为:");
            for (int z = 0; z < result.Count; z++)
            {
                for (int l = 0; l < result[z].Count; l++)
                {
                    Console.Write(result[z][l].ToString() + "\t");
                }
                Console.WriteLine();
            }
            Console.ReadLine();
        }        static int function(int i1, int i2)
        {
            return i2 - i1;
        }        static int GetSum(ArrayList list)
        {
            int sum = 0;
            foreach (int var in list)
            {
                sum += var;
            }
            return sum;
        }    }

假设有n个数，X1，X2，... Xn-1，Xn，求最大但不超过M的组合。
现在忘掉一切，单单考虑要不要最后一个数Xn。如果Xn > M，那很简单，肯定不能要Xn；
如果Xn <= M，所能得到的最好结果是什么了？
  由于Xn用掉了一些配额，剩下配额为(M-Xn)。假设我们能知道从[X1，X2，... Xn-1]中组合出最大且不超过剩下配额(M-Xn)的数M'，
  那么我们知道最好结果就是 Xn + M' 和不用Xn所能得到的最好组合，其中最大的一个。
  而不用Xn所能得到的最好组合，就是从[X1，X2，... Xn-1]中组合出最大且不超过M的数。注意到黑体部分完全跟题目几乎一样了吗，差别只在问题变小了。
我们可以用同样的方法把变小的问题变得更小，至到问题变得一目了然的程度（比如只剩下一个数）。这就叫做动态规划（Dynamic Programming）。数学描述：
定义A(j,M)是用X1~Xj能组合出的最大数（该数不超过M），那么
A(j,M) = A(j-1, M)      如果Xj>M
A(j,M) = Max( A(j-1,M), Xj + A(j-1, M-Xj) ) 如果Xj<=M代码：class Knapsack
{
    public static List<int> Solve(int[] array, int ceiling)
    {
        Node[,] matrix = new Node[array.Length + 1, ceiling + 1];
        for (int row = 0; row < matrix.GetLength(0); row++)
        {
            for (int col = 0; col < matrix.GetLength(1); col++)
            {
                if (row == 0 || col == 0)
                {
                    matrix[row, col] = new Node(0, 0, null);
                    continue;
                }                int weight = array[row - 1];
                Node defaultNode = matrix[row - 1, col];                if (weight > col)
                {
                    matrix[row, col] = new Node(0, defaultNode.Max, defaultNode);
                }
                else
                {
                    Node compondPath = matrix[row - 1, col - weight];
                    if (compondPath.Max + weight > defaultNode.Max)
                    {
                        matrix[row, col] = new Node(weight, compondPath.Max + weight, compondPath);
                    }
                    else
                    {
                        matrix[row, col] = new Node(0, defaultNode.Max, defaultNode);
                    }
                }
            }
        }         List<int> result = new List<int>();
        for(Node node = matrix[matrix.GetLength(0) - 1, matrix.GetLength(1) - 1]; node != null; node = node.Path)
        {
            if (node.Value > 0)
            {
                result.Add(node.Value);
            }
        }
        return result;    }    private class Node
    {
        public Node(int value, int max, Node path)
        {
            this.Value = value; this.Max = max; this.Path = path;
        }
        public int Value;
        public int Max;
        public Node Path;
    }
}
可以看到计算复杂度和空间复杂度都是O(WN)。如果X1~Xn不是整数，则要放大到为整数去做。

运行不了，说找不到arrylist命名空间

晕我没把引用加上你点ArrayList 然后引用下就可以了.

调试易

数组求和（一个数组有N个数求其中几个数加起来接近一个数）

解决方案 »