下料问题（Cutting Stock Problem）是生产制造中绕不开的一类组合优化问题。比如钢材经销商手上有标准长度为6000毫米的钢管，客户却需要1380毫米、1520毫米、1900毫米等不同长度的成品，每种数量还不一样。怎样在这批标准钢管上安排切割，才能让材料浪费最少、使用根数最少？这就是典型的一维下料问题。它和装箱问题（Bin Packing Problem）高度相似，但因为需求长度和数量通常固定，求解策略会有所不同。

本文使用Node.js实现求解器，一方面是因为JavaScript语法简洁，适合快速验证算法思路；另一方面Node.js可以轻松对接生产管理系统，把下料计算做成接口服务。后面会从数学模型、启发式算法、动态规划和工程整合四个层面展开。

一维下料问题的数学模型与难点

从数学角度看，一维下料问题可以描述为：给定原材料标准长度L，存在m种不同长度的需求，第i种需求长度为l_i，需求数量为d_i。需要找到一种切割方案，用最少的原材料根数满足所有需求，同时每根原料上切出的成品总长度不超过L。用整数规划表达时，通常需要枚举所有可能的切割模式（pattern），每个模式对应一根原料上切出的长度组合。例如长度6000的原料，模式可以包含两个1900加一个1380加一个820，但820不在需求里，所以模式必须由需求长度组合而成且总长不超过库存长度。

如果直接以每种模式使用次数为变量，目标是最小化模式使用总数，约束是每种需求的产出量不少于需求量，这个模型称为切割库存问题的经典列生成模型。难点在于可行切割模式的数量随着需求种类和库存长度的增加呈指数级增长，完整枚举不现实。因此实际工程中常采用启发式或混合策略。

一维下料问题虽然是NP难问题，但相比二维、三维排样，它的结构简单很多，可以利用排序、贪心和动态规划在可接受时间内得到较优解。下面介绍两种在Node.js中容易实现且效果不错的方法。

基于FFD算法的Node.js快速求解

首次适应递减（First Fit Decreasing，FFD）算法是求解一维装箱问题最常用的启发式之一。它的思路很直接：先把所有需求按长度从大到小排序，然后依次将每根成品放入第一个能容纳它的原料中；如果现有原料都放不下，就新开一根原料。这种先长后短的策略能有效减少碎片空间，实际效果通常接近最优。

用Node.js实现FFD非常简单。我们可以把每根原料的剩余长度存成数组，每次放置时遍历数组找第一个满足剩余长度大于等于成品长度的位置。下面给出对应代码。

function firstFitDecreasing(stockLength, demands) {
  // demands: [{ length: number, quantity: number }]
  const sorted = [];
  for (const d of demands) {
    for (let i = 0; i < d.quantity; i++) {
      sorted.push(d.length);
    }
  }
  sorted.sort((a, b) => b - a);
  const bins = []; // 每根原料剩余长度
  const plans = []; // 每根原料的切割方案
  for (const len of sorted) {
    let placed = false;
    for (let i = 0; i < bins.length; i++) {
      if (bins[i] >= len) {
        bins[i] -= len;
        plans[i].push(len);
        placed = true;
        break;
      }
    }
    if (!placed) {
      bins.push(stockLength - len);
      plans.push([len]);
    }
  }
  return { binCount: bins.length, waste: bins.reduce((s, r) => s + r, 0), plans };
}

上述代码中，先按需求展开数组并按降序排列，然后逐个尝试放入原料。bins数组保存每根原料的剩余可用长度，plans数组记录每根原料实际切割的长度列表。运行后能得到使用了多少根原料、总废料长度以及每根原料的切割明细。FFD的优点是速度极快，时间复杂度为O(n log n + n * m)，其中n为成品总件数，m为已开原料数。缺点是它只保证得到一个可行解，不保证全局最优。

动态规划精确求解单根原料

如果生产批量不大，我们可以对每根原料分别做精确的背包求解，目标是让单根原料的利用率最高。具体来说，给定容量为L的原料和一组待切长度，求不超过L的最大长度组合，这正是0/1背包问题。将每种需求按数量展开成独立物品后，就能用动态规划计算。

动态规划的状态转移方程很经典：dp[c]表示容量为c时能获得的最大填充长度，对于每个物品长度w，从容量L向下遍历到w，更新dp[c] = max(dp[c], dp[c - w] + w)。最终dp[L]就是单根原料最多能利用的长度。下面给出Node.js实现。

function maxFill(capacity, items) {
  // items 为展开后的长度数组
  const dp = new Array(capacity + 1).fill(0);
  for (const w of items) {
    for (let c = capacity; c >= w; c--) {
      dp[c] = Math.max(dp[c], dp[c - w] + w);
    }
  }
  return dp[capacity];
}
// 使用示例：原料长度6000，需求长度和数量
const items = [];
const demands = [
  { length: 1380, quantity: 22 },
  { length: 1520, quantity: 12 },
  { length: 1900, quantity: 8 }
];
for (const d of demands) {
  for (let i = 0; i < d.quantity; i++) items.push(d.length);
}
console.log(maxFill(6000, items));

这段代码先展开需求，然后对容量为6000的原料做背包求解。得到的最大填充长度可以帮助判断单根原料最多能容纳哪些成品，但要注意这只是单根最优，多根组合时还需要反复调用并扣除已满足的需求。实际项目中可以把FFD作为初始方案，再用背包求解器对每根原料的余料进行局部优化，通常能进一步降低废料。

完整求解器实现与工程优化

把FFD和动态规划整合到一个类中，可以构建一个更实用的下料求解器。构造函数接收原料长度和需求列表，通过expandDemands方法把需求按数量展开，solveFFD方法输出切割方案，solveOneStock方法则用于单根原料的精确填充计算。下面是一个可以直接运行的完整示例。

class CuttingStockSolver {
  constructor(stockLength, demands) {
    this.stockLength = stockLength;
    this.demands = demands;
  }
  // 展开需求为独立项
  expandDemands() {
    const items = [];
    for (const demand of this.demands) {
      for (let i = 0; i < demand.quantity; i++) {
        items.push(demand.length);
      }
    }
    return items;
  }
  // 首次适应递减算法
  solveFFD() {
    const items = this.expandDemands().sort((a, b) => b - a);
    const bins = [];
    const plans = [];
    for (const len of items) {
      let placed = false;
      for (let i = 0; i < bins.length; i++) {
        if (bins[i] >= len) {
          bins[i] -= len;
          plans[i].push(len);
          placed = true;
          break;
        }
      }
      if (!placed) {
        bins.push(this.stockLength - len);
        plans.push([len]);
      }
    }
    const waste = bins.reduce((sum, remain) => sum + remain, 0);
    const utilization = ((this.stockLength * bins.length - waste) / (this.stockLength * bins.length)) * 100;
    return {
      binCount: bins.length,
      totalWaste: waste,
      utilization: utilization.toFixed(2) + '%',
      plans
    };
  }
  // 基于动态规划的单原料最优分割
  solveOneStock(capacity, items) {
    const dp = new Array(capacity + 1).fill(0);
    for (const w of items) {
      for (let c = capacity; c >= w; c--) {
        dp[c] = Math.max(dp[c], dp[c - w] + w);
      }
    }
    return dp[capacity];
  }
}
// 运行示例
const solver = new CuttingStockSolver(6000, [
  { length: 1380, quantity: 22 },
  { length: 1520, quantity: 12 },
  { length: 1900, quantity: 8 }
]);
console.log(solver.solveFFD());

在大规模生产环境中，需求种类可能达到几十种，单种数量可能成百上千。此时直接展开所有需求会占用大量内存，FFD的遍历也可能变慢。改进思路包括：合并相同长度并记录剩余数量、使用最小堆维护原料剩余空间、采用列生成算法求解线性松弛再配合分支定界、以及利用Node.js的worker_threads并行处理多个原料尺寸。

另外，实际工程还需要考虑锯缝损耗、最小切割长度、余料可再利用等约束。这些可以在排序前对长度做预处理，或者在放置判断时加上锯缝宽度。例如每切一刀损失3毫米，那么放置成品长度时应按实际占用l_i + 3来计算，剩余长度也要相应扣减。把算法封装成REST接口后，前端传入库存长度和订单明细，后端返回切割方案和材料利用率，就能让生产计划人员直接使用。