具有范围的数字的推荐组合算法

I am currently trying to write C# code that finds multiple arrays of integers that equal a specified total when they are summed up. I would like to find these combinations while each integer in the array is given a range it can be.

我目前正在尝试编写C＃代码，它们在求和时找到多个等于指定总数的整数数组。我想找到这些组合，而数组中的每个整数都给出了它可以的范围。

For example, if our total is 10 and we have an int array of size 3 where the first number can be between 1 and 4, the second 2 and 4, and the third 3 and 6, some possible combination are [1, 3, 6], [2, 2, 6], and [4, 2, 4].

例如，如果我们的总数是10并且我们有一个大小为3的int数组，其中第一个数字可以在1到4之间，第二个数字2和4，以及第三个3和6，一些可能的组合是[1,3， 6]，[2,2,6]和[4,2,4]。

What sort of algorithm would help with solving a problem like this that can run in them most efficient amount of time? Also, what other things should I keep in mind when transitioning this problem into C# code?

什么样的算法有助于解决像这样的问题，可以在最有效的时间内运行？另外，在将此问题转换为C＃代码时，我应该记住哪些其他事项？

2 个解决方案

#1

I would do this using recursion. You can simply iterate over all possible values and see if they give a required sum.

我会使用递归来做到这一点。您可以简单地迭代所有可能的值，看看它们是否给出了所需的总和。

Input

Let's suppose we have the following input pattern:

假设我们有以下输入模式：

N S
min1 min2 min3 ... minN
max1 max2 max3 ... maxN

For your example

以你为榜样

if our total is 10 and we have an int array of size 3 where the first number can be between 1 and 4, the second 2 and 4, and the third 3 and 6

如果我们的总数是10并且我们有一个大小为3的int数组，其中第一个数字可以在1到4之间，第二个数字可以在4和4之间，第三个数字可以在3和6之间

it will be:

这将是：

3 10
1 2 3
4 4 6

Solution

We have read our input values. Now, we just try to use each possible number for our solution.

我们已经阅读了输入值。现在，我们只是尝试将每个可能的数字用于我们的解决方案。

We will have a List which will store the current path:

我们将有一个List来存储当前路径：

static List<int> current = new List<int>();

The recursive function is pretty simple:

递归函数非常简单：

private static void Do(int index, int currentSum)
{
    if (index == length) // Termination
    {
        if (currentSum == sum) // If result is a required sum - just output it
            Output();
        return;
    }

    // try all possible solutions for current index
    for (int i = minValues[index]; i <= maxValues[index]; i++) 
    {
        current.Add(i);
        Do(index + 1, currentSum + i); // pass new index and new sum
        current.RemoveAt(current.Count() - 1);
    }
}

For non-negative values we can also include such condition. This is the recursion improvement which will cut off a huge amount of incorrect iterations. If we already have a currentSum greater than sum then it is useless to continue in this recursion branch:

对于非负值，我们也可以包括这样的条件。这是递归改进，它将切断大量不正确的迭代。如果我们已经有一个大于sum的currentSum，那么在这个递归分支中继续是没用的：

if (currentSum > sum) return;

Actually, this algorithm is a simple "find combinations that give a sum S" problem solution with one difference: inner loop indices within minValue[index] and maxValue[index].

实际上，这个算法是一个简单的“查找组合，给出和S”问题解决方案，有一个区别：minValue [index]和maxValue [index]内的内循环索引。

Demo

Here is the working IDEOne demo of my solution.

这是我的解决方案的IDEOne演示。

#2

You cannot do much better than nested for loops/recursion. Though if you are familiar with the 3SUM problem you will know a little trick to reduce the time complexity of this sort of algorithm! If you have n ranges then you know what number you have to pick from the nth range after you make your first n-1 choices!

你不能比嵌套for循环/递归做得更好。虽然如果你熟悉3SUM问题，你会知道一个小技巧来减少这种算法的时间复杂度！如果你有n个范围，那么在你做出第一个n-1选择之后，你知道你必须从第n个范围中选择什么数字！

I will use an example to walk through my suggestion.

我将用一个例子来说明我的建议。

if our total is 10 and we have an int array of size 3 where the first number can be between 1 and 4, the second 2 and 4, and the third 5 and 6

如果我们的总数是10并且我们有一个大小为3的int数组，其中第一个数字可以在1到4之间，第二个数字可以在4和4之间，第三个数字可以在5和6之间

First of all lets process the data to be a bit nicer to deal with. I personally like the idea of working with ranges that start at 0 instead of arbitrary numbers! So we subtract the lower bounds from the upper bounds:

首先，让处理数据更好一些。我个人喜欢使用从0开始而不是任意数字的范围的想法！所以我们从上界减去下界：

(1 to 4) -> (0 to 3)
(2 to 4) -> (0 to 2)
(5 to 6) -> (0 to 1)

Of course now we need to adjust our target sum to reflect the new ranges. So we subtract our original lower bounds from our target sum as well!

当然，现在我们需要调整目标总和以反映新的范围。所以我们也从目标总和中减去原始的下界！

TargetSum = 10-1-2-5 = 2

Now we can represent our ranges with just the upper bound since they share a lower bound! So a range array would look something like:

现在我们可以用上限来表示我们的范围，因为它们共享下限！因此范围数组看起来像：

RangeArray = [3,2,1]

Lets sort this (it will become more obvious why later). So we have:

让我们对此进行排序（以后会变得更加明显）。所以我们有：

RangeArray = [1,2,3]

RangeArray = [1,2,3]

Great! Now onto the beef of the algorithm... the summing! For now I will use for loops as it is easier to use for example purposes. You will have to use recursion. Yeldar's code should give you a good starting place.

大！现在进入算法的牛肉......总结！现在我将使用for循环，因为它更容易用于示例目的。你将不得不使用递归。耶尔达的代码应该给你一个很好的起点。

result = []
for i from 0 to RangeArray[0]:
    SumList = [i]
    newSum = TargetSum - i
    for j from 0 to RangeArray[1]:
        if (newSum-j)>=0 and (newSum-j)<=RangeArray[2] then
            finalList = SumList + [j, newSum-j]
            result.append(finalList)

Note the inner loop. This is what was inspired by the 3SUM algorithm. We take advantage of the fact that we know what value we have to pick from the third range (since it is defined by our first 2 choices).

注意内循环。这是受3SUM算法启发的。我们利用这样一个事实，即我们知道我们必须从第三个范围中选择什么值（因为它是由我们的前两个选择定义的）。

From here you have to of course re-map the results back to the original ranges by adding the original lowerbounds to the values that came from the corresponding ranges.

从这里开始，您必须通过将原始下边界添加到来自相应范围的值，将结果重新映射回原始范围。

Notice that we now understand why it may be a good idea to sort RangeList. The last range gets absorbed into the secondlast range's loop. We want the largest range to be the one that does not loop.

请注意，我们现在理解为什么对RangeList进行排序可能是个好主意。最后一个范围被吸收到secondlast范围的循环中。我们希望最大范围是不循环的范围。

I hope this helps to get you started! If you need any help translating my pseudocode into c# just ask :)

我希望这有助于你开始！如果您需要任何帮助将我的伪代码翻译成c＃，请问:)