c# - 递归算法中的大数时出现 StackOverflowException。优化？

Question

任务:我需要将一批包裹分发到不同容量的容器中。
每个容量都有限制:最小和最大包裹数。
包裹数量应等于或小于所选容器容量的总和。
容量存储在数据库中。包总和由用户提示，可以是十进制。
结果应该是每个容器的容器容量的集合。
结果计数没有限制。
我有一个用 C# 编写的递归解决方案，但是对于大包总和，它会因 StackOverflowException 而崩溃。

// returns all combinations of capacity max and min values which package sum could include
static IEnumerable<List<int>> GetCombinations(int[] set, int sum, List<int> values)
{
    for (var i = 0; i < set.Length; i++)
    {
        var left = sum - set[i];
        var vals = new List<int>(values);
        vals.Add(set[i]);

        if (left == 0)
        {
            yield return vals;
        }
        else
        {
            int[] possible = set.Where(n => n <= sum).ToArray();
            if (possible.Length > 0)
            {
                foreach (var s in GetCombinations(possible, left, vals))
                {
                    yield return s;
                }
            }
        }
    }
}

调用 packageCapacities 包含属性 Count(实际为 MaxCount)和 MinCount 的代码:

var allCapacityValues = packageCapacities
    .SelectMany(x => Enumerable.Range((int)x.MinCount, (int)x.Count - (int)x.MinCount + 1))
    .OrderByDescending(x => x)
    .ToArray();
// gets first combination, sort numbers in it and distinct it
var combination = GetCombinations(allCapacityValues, (int)Math.Ceiling(contentData.FactCount), new List<int>())
    .Select(x => x.OrderByDescending(o => o))
    .Distinct(new EnumerableComparer<int>())
    .FirstOrDefault();

其中有两个容量和 13 的总和，分为 3 个容器尺寸。

可重现代码:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Data.Services
{
    public class ContainerGenerationService1
    {
        public void GenerateContainersWorks()
        {
            int capacity1Min = 4;
            int capacity1Max = 5;
            int capacity2Min = 2;
            int capacity2Max = 2;
            int[] set = Enumerable.Range(capacity1Min, capacity1Max - capacity1Min + 1)
                .Concat(Enumerable.Range(capacity2Min, capacity2Max - capacity2Min + 1))
                .ToArray();
            int sum = 13;

            var combination = GetCombinations(set, sum, new List<int>())
              .Select(x => x.OrderByDescending(o => o))
              .Distinct(new EnumerableComparer<int>())
              .FirstOrDefault();
        }

        public void GenerateContainersFails()
        {
            int capacity1Min = 3;
            int capacity1Max = 9;
            int[] set = Enumerable.Range(capacity1Min, capacity1Max - capacity1Min + 1).ToArray();
            int sum = 999999;

            var combination = GetCombinations(set, sum, new List<int>())
              .Select(x => x.OrderByDescending(o => o))
              .Distinct(new EnumerableComparer<int>())
              .FirstOrDefault();
        }


        static IEnumerable<List<int>> GetCombinations(int[] set, int sum, List<int> values)
        {
            for (var i = 0; i < set.Length; i++)
            {
                var left = sum - set[i];
                var vals = new List<int>(values);
                vals.Add(set[i]);

                if (left == 0)
                {
                    yield return vals;
                }
                else
                {
                    int[] possible = set.Where(n => n <= sum).ToArray();
                    if (possible.Length > 0)
                    {
                        foreach (var s in GetCombinations(possible, left, vals))
                        {
                            yield return s;
                        }
                    }
                }
            }
        }

        class EnumerableComparer<T> : IEqualityComparer<IEnumerable<T>> where T : IComparable<T>
        {
            public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
            {
                if (first == second)
                    return true;
                if ((first == null) || (second == null))
                    return false;

                return new HashSet<T>(first).SetEquals(second);
            }

            public int GetHashCode(IEnumerable<T> enumerable)
            {
                return enumerable.OrderBy(x => x)
                  .Aggregate(1, (current, val) => current + val.GetHashCode());
            }
        }
    }
}

调用代码:

var svc = new ContainerGenerationService1();
svc.GenerateContainersWorks(); // works
svc.GenerateContainersFails(); // fails with StackOverflowException

Answer 1

堆栈溢出绝不是您的代码的唯一问题，但让我们从那里开始。 GetCombinations递归调用自身。当您收到数十万次调用时，您就会耗尽堆栈。在这种情况下您不能使用系统堆栈，您需要更大的数据存储。
您在这里只是在寻找一种解决方案，但代码显然是为了返回所有不同的集合而编写的。但是您应该重新考虑该方法。您生成所有变体，然后选择唯一的集合并丢弃其余的集合。这是非常昂贵的。就像，差了几个数量级。您应该直接生成不同的集合。就像，如果您有数字 6，那么下一个数字可以是 6 或 5 或 4，但不能是 7。
下一个大问题是没有解决方案的情况。如果存在，您可能会很快找到一些解决方案。但如果没有，您将在许多组合中循环。您可以使用动态规划来解决这个问题。它会告诉您哪些金额对您拥有的容器有效，哪些无效。您可以使用它来进一步提高递归效率。
您新建 List每次从函数返回时。这是安全的方法。但是您通常可以只返回相同的列表并对其进行修改。对于类似 GetCombinations(...).Count() 的情况它更有效率。让我们把它放在一起

static IEnumerable<List<int>> GetCombinations(int[] set, int sum)
{
    var orderedSet = set.Distinct().OrderByDescending(o => o).ToArray();

    bool[] valid = new bool[sum + 1];
    valid[0] = true;
    for (int i = 0; i < sum; ++i)
    {
        if (valid[i])
        {
            for (int j = 0; j < orderedSet.Length; ++j)
            {
                int next = i + orderedSet[j];
                if (next < valid.Length)
                {
                    valid[next] = true;
                }
            }
        }
    }

    if (!valid[sum])
    {
        return new List<int>[0]; //no solution
    }

    return GetCombinationsRecurse(orderedSet, sum, new List<int>(), valid, 0);
    //return GetCombinationsNoRecurse(orderedSet, sum, valid);
}      

static IEnumerable<List<int>> GetCombinationsRecurse(int[] set, int sum, 
    List<int> values, bool[] valid, int setIterator)
{
    for (var i = setIterator; i < set.Length; i++)
    {
        var left = sum - set[i];
        if (left < 0 || !valid[left])
        {
            continue;
        }

        values.Add(set[i]);

        if (left == 0)
        {
            yield return values;
        }
        else
        {
            foreach (var s in GetCombinationsRecurse(set, left, values, valid, i))
            {
                yield return s;
            }
        }
        values.RemoveAt(values.Count - 1);
    }
}

我在这里给出了递归版本，因为它与您的原始代码匹配并且更易于遵循。但是大数字的堆栈溢出显然仍然存在。递归函数总是可以重写为非递归版本。您需要使用一些数据结构而不是系统堆栈。堆栈或数组或其他任何东西。但它往往不漂亮

static IEnumerable<List<int>> GetCombinationsNoRecurse(int[] set, int sum, bool[] valid)
{
    List<int> sums = new List<int>() { 0 };
    List<int> setIterators = new List<int>() { 0 };
    int iter = 0;
    List<int> values = new List<int>() { set[iter] };

    while (true)
    {
        int actSum = sums[iter] + values[iter];
        int left = sum - actSum;
        if (left == 0)
        {
            yield return values;
        }

        if (left <= 0 || !valid[left])
        {
            while (++setIterators[iter] >= set.Length)
            {
                if (--iter < 0) { yield break; }
                values.RemoveAt(values.Count - 1);
            }
            values[iter] = set[setIterators[iter]];
            continue;
        }

        { // left > 0
            if (sums.Count > iter + 1)
            {
                sums[iter + 1] = actSum;
                setIterators[iter + 1] = setIterators[iter];
            }
            else
            {
                sums.Add(actSum);
                setIterators.Add(setIterators[iter]);
            }

            values.Add(values[iter]);
            iter++;
        }
    }
}