将长度为N的材料切割成特定的长度，求最少需要的材料数量

Question

给定一个长度列表，我们需要将长度为 N 的原始 material 剪切为列表中指定的长度。请找出我们需要的 material 的最小数量。

示例：

list = [6000, 3800, 1290, 1190, 341]
N = 6000

输出：

前6000需要一个完整的material，3800+1290+341=5431，共用一个material，剩下的1190需要一个单独的material.So我们需要3materials 至少。

还有另一种描述问题的方法。

从给定的 array.The 元素中的元素构造子数组不能是 reused.The 子数组的总和不能大于 N.Find 子数组的最小数量。

使用上面列表中的元素的子数组如下。

[[6000], [3800,1290,341], [1190]]

Answer 1

它是“Bin packing problem”，这是 JavaScript 中首次拟合（排序）算法的实现。

    function firstFit(cutsUnsorted, materialLength) {
      const cuts = [...cutsUnsorted].sort((a, b) => b - a) // Sort decreasing for better result
      const cutsNumber = cuts.length
      const materialRemaining = new Array(cutsNumber).fill(0)
      const cutInMaterial = new Array(cutsNumber).fill(-1)
      let materialRequired = 0

      // Iterate through cuts
      for (let cutIndex = 0; cutIndex < cutsNumber; cutIndex++) {
        let materialIndex

        // Find the best material that can get cuts[cutIndex]
        for (materialIndex = 0; materialIndex < materialRequired; materialIndex++) {
          if (materialRemaining[materialIndex] >= cuts[cutIndex]) {
            materialRemaining[materialIndex] =
              materialRemaining[materialIndex] - cuts[cutIndex]
            cutInMaterial[cutIndex] = materialIndex
            break
          }
        }

        // If no material could get cuts[cutIndex], use a new material
        if (materialIndex === materialRequired) {
          materialRemaining[materialRequired] = materialLength - cuts[cutIndex]
          materialRequired++
          cutInMaterial[cutIndex] = materialIndex
        }
      }

      // Format and print cutInMaterial start
      let log = '['
      for (let i = 0; i < materialRequired; i++) {
        log = `${log}[`
        for (let j = 0; j < cutsNumber; j++) {
          if (cutInMaterial[j] === i) {
            log = `${log}${cuts[j]},`
          }
        }
        log = `${log.slice(0, -1)}],`
      }
      console.log(`${log.slice(0, -1)}]`)
      // Format and print cutInMaterial end

      return materialRequired
    }

    // ***** Start program
    const cuts = [6000, 3800, 1290, 1190, 341]
    const materialLength = 6000

    console.log(
      'Number of material required (firstFit algorithm):',
      firstFit(cuts, materialLength)
    )

将长度为N的材料切割成特定的长度，求最少需要的材料数量

Cut the materials of length N into specific lengths, Find minimun number of materials we need

algorithm

dynamic-programming