系列计算
我有一些随机整数
99 20 30 1 100 400 5 10 我必须从这些整数的任意组合中找到一个总和，它与给定的数字最接近（等于或多但不少）
183
这样做最快，最准确的方法是什么？
如果您的数字很小，您可以使用简单的动态编程（DP）技术。 不要让这个名字吓到你。 这种技术是可以理解的。 基本上你将更大的问题分解为子问题。
在这里我们定义问题can[number] 。 如果number可以从文件中的整数构造，则can[number]为true ，否则为false 。 很明显， 0可以通过完全不使用任何数字来构造，因此can[0]是true 。 现在，您尝试使用输入文件中的每个数字。 我们试着看看总和j是否可以实现。 如果already achieved sum + current number we try == j ，那么j显然是可以实现的。 如果要跟踪哪些数字构成特定总和，请使用额外的prev数组，该数组存储最后使用的数字以进行总和。 请参阅下面的代码以实现此想法：
int UPPER_BOUND = number1 + number2 + ... + numbern //The largest number you can construct bool can[UPPER_BOUND + 1]; //can[number] is true if number can be constructed can[0] = true; //0 is achievable always by not using any number int prev[UPPER_BOUND + 1]; //prev[number] is the last number used to achieve sum "number" for (int i = 0; i < N; i++) //Try to use every number(numbers[i]) from the input file { for (int j = UPPER_BOUND; j >= 1; j--) //Try to see if j is an achievable sum { if (can[j]) continue; //It is already an achieved sum, so go to the next j if (j - numbers[i] >= 0 && can[j - numbers[i]]) //If an (already achievable sum) + (numbers[i]) == j, then j is obviously achievable { can[j] = true; prev[j] = numbers[i]; //To achieve j we used numbers[i] } } } int CLOSEST_SUM = -1; for (int i = SUM; i <= UPPER_BOUND; i++) if (can[i]) { //the closest number to SUM(larger than SUM) is i CLOSEST_SUM = i; break; } int currentSum = CLOSEST_SUM; do { int usedNumber = prev[currentSum]; Console.WriteLine(usedNumber); currentSum -= usedNumber; } while (currentSum > 0);
这似乎是一个类似背包的问题 ，你的整数值将是每个项目的“权重”，每个项目的“利润”是1，并且你正在寻找最少数量的项目以完全相加背包的最大允许重量。
这是SUBSET-SUM问题的变体，也是像SUBSET-SUM一样的NP-Hard。
但是如果涉及的数字很小，则存在伪多项式时间算法。 查看：
http://en.wikipedia.org/wiki/Subset_sum_problem
好的更多细节。
以下问题：
给定一个整数数组和整数a，b，是否存在一些子集，其总和位于区间[a，b]中是NP-Hard。
这是因为我们可以通过选择a = b = 0来求解子集和。
现在这个问题很容易减少到你的问题所以你的问题也是NP-Hard。
现在您可以使用上面wiki链接中提到的多项式时间近似算法。
给定N个整数的数组，目标S和近似阈值c，
存在多项式时间近似算法（涉及1 / c），其告知在区间[（1-c）S，S]中是否存在子集和。
您可以重复使用（通过某种forms的二分搜索）来找到您需要的最佳近似值。 注意你也可以在[S，（1 + c）S]的间隔使用它，而背包只会给你一个解决方案<= S.
当然可能有更好的算法，实际上我可以赌它。 网上应该有大量的文献。 您可以使用的一些搜索术语：子集和的近似算法，伪多项式时间算法，动态规划算法等。
一个简单的暴力方法是读取文本，将其解析为数字，然后遍历所有组合，直到找到所需的总和。
更快的解决方案是对数字进行排序，然后…将最大数字加到您的总和中，是否太大了？ 如果是这样，把它拿下来尝试下一个最小的。 如果总和太小，请添加下一个最大数字并重复。 继续添加数字，不要让总和超过目标。 当你击中目标时完成。
请注意，当您回溯时，您可能需要回溯多个级别。 听起来像递归的好例子……
如果数字很大，您可以将其转换为整数程序。 使用Mathematica的求解器，它可能看起来像这样
nums = {99, 20, 30 , 1, 100, 400, 5, 10}; vars = a /@ Range@Length@nums; Minimize[(vars.nums - 183)^2, vars, Integers]
您可以对值列表进行排序，找到大于目标的第一个值，并开始专注于小于目标的值。 找到最接近目标的总和而不经过，然后将其与大于目标的第一个值进行比较。 如果最近总和与目标之间的差异小于大于目标的第一个值与目标之间的差异，那么您将得到最接近的总和。
有点儿，但我认为逻辑悬而未决。