推荐的数字范围组合算法

Question

我现在正在尝试编写C#代码，找到多个整数数组，使它们被加起来等于指定的总和。我想在每个数组元素被赋予一个范围的情况下找到这些组合。

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

什么样的算法可以帮助解决这样的问题，并能在最高效的时间内运行？还有，在将该问题转换为C#代码时，我应该注意哪些其他事项？

- Lotzi11

---

我会使用递归来实现这个，但很可能它不是最优解。 - Yeldar Kurmangaliyev

此处描述的算法应该完美地适用于基本的组合生成器。为了生成输入并过滤输出，Enumerable.Range 和 Linq .Where 将是最简单的选择。 - Martheen

你介意我给你一个带解释的解决方案吗？还是你不想让任何人帮助你？ - Yeldar Kurmangaliyev

随意以任何方式解释这个。 - Lotzi11

Answer 1

我会使用递归来实现。您可以简单地迭代所有可能的值并查看它们是否给出所需的总和。

输入

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

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

针对你的例子

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

那么它将是这样的:

3 10
1 2 3
4 4 6

解决方案

我们已经读取了输入值。现在，我们只需尝试使用每个可能的数字来解决问题。

我们将拥有一个List，它将存储当前路径：

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

这段文本的英译中文如下：

递归函数相当简单：

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

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

if (currentSum > sum) return;

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

演示

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

- Yeldar Kurmangaliyev

Answer 2

您最好使用嵌套的for循环/递归。但是，如果您熟悉3SUM问题，则会知道一些技巧来降低此类算法的时间复杂度！如果您有n个范围，则在做出第一个n-1个选择后，您知道必须从第n个范围中选择哪个数字！

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

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

首先，让我们处理数据使其更易处理。我个人喜欢使用从0开始的范围的想法，而不是任意数字！因此，我们将下限从上限中减去：

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

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

TargetSum = 10-1-2-5 = 2

现在我们只需要表示上限，因为它们共享一个下限！因此，范围数组将如下所示：

RangeArray = [3,2,1]

让我们先对此进行排序（稍后会更明显为什么）。所以我们有：

RangeArray = [1,2,3]

太好了！现在进入算法的核心...求和！目前我将使用for循环，因为它更容易用于示例目的。您将需要使用递归。Yeldar的代码应该为您提供一个良好的起点。

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)

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

从这里开始，当然需要通过将原始下限添加到来自相应范围的值来将结果重新映射回原始范围。

请注意，现在我们明白为什么对于RangeList进行排序可能是个好主意。最后一个范围被吸收到倒数第二个范围的循环中。我们希望最大的范围不参与循环。

我希望这可以帮助您入门！如果您需要将我的伪代码翻译成C#，请随时询问 :)

- Michael S Priz

---

在第七行代码（finalList = SumList + [j, newSum-j]）中，我不理解[j, newSum-j]是什么意思。你能解释一下吗？ - Lotzi11

SumList + [j, newSum-j] 的意思是将 j 和 newSum-j 添加到 SumList 中。其中，j 是我们选择的中间范围内的元素。由于我们已经选择了 2 个数字，并且只有 3 个范围可供选择，因此最终的选择已经为我们做出！我们必须选择 newSum-j！ - Michael S Priz