系列计算 [英] Series calculation

问题描述

我有一些随机整数像

99 20 30 1 100 400 5 10

我要找到这些整数的任意组合的总和最接近（同等或以上，但不低于），像

I have to find a sum from any combination of these integers that is closest(equal or more but not less) to a given number like

183

什么是这样做的最快速和准确的方法是什么？

what is the fastest and accurate way of doing this?

推荐答案

如果您的号码是小，你可以使用一个简单的动态规划（DP）技术。不要让这个名字吓唬你。该技术是非常可以理解的。基本上，你打破了更大的问题划分为若干子。

If your numbers are small, you can use a simple Dynamic Programming(DP) technique. Don't let this name scare you. The technique is fairly understandable. Basically you break the larger problem into subproblems.

在这里我们定义问题是可以[编号] 。如果号可从整数在文件中构造的，则可以[编号] 是真，否则是假。很明显， 0 是施工的不使用任何数字可言，所以可以[0] 是真。现在，您尝试使用每个数字的输入文件。我们尝试看看是否总和Ĵ是可以实现的。如果已达到总和+当前一些我们试图==Ĵ，然后Ĵ显然是可以实现的。如果你想跟踪哪些数字做了一个特别的总和，使用一个额外的 $ P $光伏阵列，用于存储最近使用的数量，使之和。请参见下面的$ C $下这个想法的实现：

Here we define the problem to be can[number]. If the number can be constructed from the integers in your file, then can[number] is true, otherwise it is false. It is obvious that 0 is constructable by not using any numbers at all, so can[0] is true. Now you try to use every number from the input file. We try to see if the sum j is achievable. If an already achieved sum + current number we try == j, then j is clearly achievable. If you want to keep track of what numbers made a particular sum, use an additional prev array, which stores the last used number to make the sum. See the code below for an implementation of this idea:

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);

这篇关于系列计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！