类似背包问题数据分组

Question

大家好，请教一个问题。
假设我产品有200多个，200多个有各种各样价格。然后想做个礼盒，礼盒要求：1.每个礼盒产品数量是要6个，2、每个礼盒6个产品价格求和是在200-300区间， 符合条件的6个作为一组进行分组，不符合条件就单独拿出来不做处理。

产品价格如下：

Answer 1

const uniform = (a: number, b: number): number => {
  return a + Math.floor((b - a) * Math.random())
}

type Product = {
  id: number
  price: number
}

/**
 * 用双指针，每次挑选出一个价格最高的，再从价格最低的中挑出五个，相加如果价格高于300，就将r指针减一
 * @param products
 */
const grouping = (products: Product[]) => {
  let l = 0
  let r = products.length - 1
  let ans: Product[][] = []
  products.sort((a, b) => a.price - b.price)

  const presum: number[] = Array.from({ length: products.length + 1 })
  presum[0] = 0

  for (let i = 1; i <= products.length; ++i) {
    presum[i] = presum[i - 1] + products[i - 1].price
  }

  mainLoop: while (l + 5 <= r) {
    /**
     * 该商品的价格直接超过了300我们直接忽略他
     */
    if (products[r].price > 300) {
      --r
      continue
    }

    let largeCount = 1

    do {
      let curR = r - largeCount + 1
      //当largeCount取6时会导致 curL < l，所以在包一层Math.max
      let curL = Math.max(l + 5 - largeCount + 1, l)
      const sum = presum[curL] - presum[l] + presum[r + 1] - presum[curR]

      if (sum < 200) {
        /**
         * 小于200，再多选取一件高价商品的
         */
        if (largeCount + 1 < 6) ++largeCount
        // 6件商品都选取仍然凑不够200，没有更多解了，直接break
        else break mainLoop
      } else if (sum > 300) {
        /**
         * 和大于300剔除一件高价商品,通过--r直接把他剔除出区间
         */
        --r
        continue mainLoop
      } else {
        const cand = products.slice(l, curL).concat(products.slice(curR, r + 1))
        ans.push(cand)
        l = curL
        r = curR - 1
        break
      }
    } while (true)
  }

  return ans
}

console.log(
  grouping(
    Array.from({ length: 200 }, (_, i) => ({
      id: i,
      price: uniform(30, 350),
    }))
  )
)