数组元素最优分组折扣计算问题求解及现有JavaScript代码优化指导

原代码已知问题 #

• dis折扣函数逻辑错误：重复判断len===3，缺少len===2的5%折扣分支，导致折扣计算完全错误
• 变量声明错误：total用const声明无法修改，计算总价时引用的slen未定义
• 核心逻辑缺陷：采用贪心策略每次优先凑最大款数的分组，无法覆盖更优的组合方案（如示例中5+3组合不如4+4组合划算）

优化思路 #

采用记忆化递归枚举所有合法分组组合，计算所有可能的总价后取最小值：

1. 将各款T恤剩余数量存储为长度为5的数组，每次递归前对数组降序排序，相同数量分布的状态可以复用计算结果，避免重复递归
2. 每次递归时枚举当前可选择的分组大小（从最大的5到1，只要当前有对应数量的不同款即可）
3. 计算当前分组价格 + 剩余库存递归计算的价格，取所有组合中的最小值作为当前状态的最优解

优化后代码 #

// 不同分组大小对应的折扣率
const discountMap = {
  1: 0,
  2: 0.05,
  3: 0.1,
  4: 0.2,
  5: 0.25
}
// 记忆化缓存，key是排序后的库存字符串，value是对应最优总价
const memo = new Map()

const calculateMinCost = (stock) => {
  // 过滤掉库存为0的款，降序排序后做缓存key
  const sortedStock = stock.filter(num => num > 0).sort((a, b) => b - a)
  const key = sortedStock.join(',')
  // 缓存命中直接返回
  if (memo.has(key)) return memo.get(key)
  // 库存为空返回0
  if (sortedStock.length === 0) return 0

  let minCost = Infinity
  // 枚举当前可以凑的分组大小，最大为当前不同款的数量，最小为1
  const maxGroupSize = sortedStock.length
  for (let groupSize = 1; groupSize <= maxGroupSize; groupSize++) {
    // 生成新的库存：前groupSize个款各减1
    const newStock = [...sortedStock]
    for (let i = 0; i < groupSize; i++) {
      newStock[i] -= 1
    }
    // 计算当前分组价格 + 剩余库存的最优价格
    const currentGroupCost = groupSize * 8 * (1 - discountMap[groupSize])
    const totalCost = currentGroupCost + calculateMinCost(newStock)
    // 更新最小值
    if (totalCost < minCost) {
      minCost = totalCost
    }
  }
  // 存入缓存
  memo.set(key, minCost)
  return minCost
}

const cart = (items) => {
  // 初始化库存，索引0-4对应编码1-5的T恤
  const stock = new Array(5).fill(0)
  items.forEach(code => {
    stock[code - 1] += 1
  })
  // 计算前清空缓存，避免多次调用互相影响
  memo.clear()
  return calculateMinCost(stock)
}

// 测试示例
const cost = cart([1,1,2,2,3,3,4,5]);
console.log("cost: ", cost); // 输出 51.2

代码说明 #

• 记忆化缓存大幅降低了重复状态的计算开销，即使是几十件的购物车也可以快速计算出结果
• 枚举所有合法分组组合，保证可以找到全局最优解，不会出现贪心策略的局部最优问题
• 修复了原代码所有语法和逻辑错误，测试示例可以正确输出预期的51.2美元的结果

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