c# - 带范围的数字的推荐组合算法

Question

我目前正在尝试编写 C# 代码来查找多个整数数组，这些整数数组在求和时等于指定的总数。我想找到这些组合，同时给数组中的每个整数一个范围。

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

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

Answer 1

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

输入

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

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

以你为例

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

它将是:

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 demo我的解决方案。