假如数组 1，2，3，4，5
我要找出和为8的
如果要找范围是2-4个元素组成和为8的话.先找3个元素的组合
1,2,5
1,3,4
如果找不到的话再找2个元素的.
3,5,
再找不到再找4个元素的.
如果都找不到就找一个3个元素的.小于7的组合.以此类推.....
元素个数不超过500，这个和的范围不超过3000.
有一位牛人的
解答如下
-----------
设要求的和为m，元素的个数为n，k个元素的和为m，极端情况下k = n。
利用DP解01背包，时间O(m*n*k)，空间O(m*n))，
详细说一下就是：
定义一个m*n*n的2维数组matrix[i,j]，用来记录i个元素的和为j的情况下是否有解。这样的话用一个bool数组即可，但这样会出现重复选择的情况，同时为了最后构造解方便，数组中的数据用来记录有解情况下的最后一个元素的下标。
初始化martix[i,j] = -1
如果matrix[i,j] >= 0，则matrix[i + 1, j + item[i]] = i。
这样用一个三重循环，可以求得所有matrix[i,j]的值，然后再遍历一下所有的i,j的值，找出最合适的解。
再根据matrix[i,j]的值，构造解。用滚动数组应该可以让空间复杂度变为O(m)。
int[] items = new int[] { 2, 3, 4, 5, 6, 7, 8 }; int sum = 35, count = 7; int[,] matrix = new int[items.Length + 1, sum + 1]; for (int i = 0; i < matrix.GetLength(0); i++) for (int j = 0; j < matrix.GetLength(1); j++) matrix[i, j] = -2; matrix[0, 0] = -1; for (int i = 0; i < items.Length; i++) { for (int j = 0; j <= sum; j++) { if (matrix[i, j] == -2) continue; for (int k = matrix[i, j] + 1; k < items.Length; k++) { if (j + items[k] > sum) break; if (matrix[i + 1, j + items[k]] == -2) matrix[i + 1, j + items[k]] = k; else matrix[i + 1, j + items[k]] = Math.Min(matrix[i + 1, j + items[k]], k); } } } if (matrix[count, sum] == -2) Console.WriteLine("{0} 个数的和 = {1} 无解", count, sum); else { while (sum > 0) { Console.WriteLine(items[matrix[count, sum]]); sum -= items[matrix[count, sum]]; count--; } }
但是这个针对的是整数 类型，实际情况可能是double类型
当用服double*100转换后。够建数组大了100倍。速度慢了好一些，大虾位可否想个办法直接是double的情形也能适用。
3 个解决方案
#1
上次不是给你了一个思路么？不行
#2
这个是什么？
#3
#1
上次不是给你了一个思路么？不行
#2
这个是什么？
#3