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

本文关键字：组合 算法 数字 范围 | 更新日期: 2023-09-27 18:08:19

我目前正在尝试编写c#代码，查找多个整数数组，当它们相加时等于指定的总数。我想找到这些组合，而数组中的每个整数被给定一个范围，它可以。

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

什么样的算法可以帮助解决这样一个问题，可以在他们最有效的时间内运行?此外，在将这个问题转换为c#代码时，我还应该记住哪些其他事情?

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

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

输入

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

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

对于您的示例

，如果我们的总数是10，并且我们有一个大小为3的int数组，其中第一个数字可以在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演示。

没有比嵌套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#就问:)

相关文章：