如何避免随钢筋切割规格数量增加编写多层嵌套循环？求通用算法

1. 递归回溯法 #

递归可以动态适配任意数量的切割规格，核心思路是逐个处理每种规格，递归遍历该规格的可能使用数量，同时跟踪已用总长度，处理完所有规格后再检查废料是否符合要求。

示例代码（C#）：

// 按需替换为你的切割规格、目标长度和废料阈值
double[] BarCut = { /* 切割规格数组 */ };
double targetLength = 20;
double maxWaste = 1;

void FindValidCombinations(int index, int[] counts, double currentTotal)
{
    // 处理完所有规格，验证废料是否合规
    if (index == BarCut.Length)
    {
        double waste = targetLength - currentTotal;
        if (waste >= 0 && waste <= maxWaste)
        {
            string result = string.Join(", ", counts.Select((cnt, i) => $"{cnt}{(char)('A' + i)}"));
            Console.WriteLine($"{result}, TL={currentTotal:F2}, waste={waste:F2}");
        }
        return;
    }

    // 计算当前规格的最大可用数量，避免无效循环
    double remaining = targetLength - currentTotal;
    int maxCount = (int)(remaining / BarCut[index]);
    maxCount = Math.Max(0, maxCount);

    // 遍历当前规格的所有可能使用数量
    for (int cnt = 0; cnt <= maxCount; cnt++)
    {
        counts[index] = cnt;
        FindValidCombinations(index + 1, counts, currentTotal + cnt * BarCut[index]);
    }
}

// 启动递归查找
int[] counts = new int[BarCut.Length];
FindValidCombinations(0, counts, 0);

2. 迭代式组合生成（无需递归） #

如果不想用递归，可以用栈模拟递归过程，保存每一步的状态（当前处理的规格索引、已选数量数组、当前总长度），逐个弹出状态处理直到栈为空。

示例代码（C#）：

double[] BarCut = { /* 切割规格数组 */ };
double targetLength = 20;
double maxWaste = 1;

// 栈中存储状态：(当前规格索引, 已选数量数组, 当前总长度)
Stack<Tuple<int, int[], double>> stack = new Stack<Tuple<int, int[], double>>();
stack.Push(Tuple.Create(0, new int[BarCut.Length], 0.0));

while (stack.Count > 0)
{
    var state = stack.Pop();
    int index = state.Item1;
    int[] counts = state.Item2;
    double currentTotal = state.Item3;

    if (index == BarCut.Length)
    {
        double waste = targetLength - currentTotal;
        if (waste >= 0 && waste <= maxWaste)
        {
            string result = string.Join(", ", counts.Select((cnt, i) => $"{cnt}{(char)('A' + i)}"));
            Console.WriteLine($"{result}, TL={currentTotal:F2}, waste={waste:F2}");
        }
        continue;
    }

    double remaining = targetLength - currentTotal;
    int maxCount = (int)(remaining / BarCut[index]);
    maxCount = Math.Max(0, maxCount);

    // 倒序入栈保证遍历顺序和递归一致（可选）
    for (int cnt = maxCount; cnt >= 0; cnt--)
    {
        int[] newCounts = (int[])counts.Clone();
        newCounts[index] = cnt;
        stack.Push(Tuple.Create(index + 1, newCounts, currentTotal + cnt * BarCut[index]));
    }
}

关键优化点 #

• 动态计算最大数量：不再固定写死循环上限（比如示例中的50），而是根据剩余可切割长度计算当前规格的最大使用量，大幅减少无效循环。
• 自动剪枝：通过剩余长度计算直接排除超过目标长度的情况，避免不必要的计算。

这两种方法都能适配任意数量的切割规格，无需修改核心逻辑，仅需更新BarCut数组即可。

内容的提问来源于stack exchange，提问作者Noel