类似背包问题数据分组

_Hay
  • 3
新手上路,请多包涵

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

产品价格如下:

回复
阅读 221
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),
    }))
  )
)
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏