1774.最接近目标价格的甜点成本.md

1774.最接近目标价格的甜点成本

/*
 * @lc app=leetcode.cn id=1774 lang=typescript
 *
 * [1774] 最接近目标价格的甜点成本
 */

// @lc code=start
function closestCost(baseCosts: number[], toppingCosts: number[], target: number): number {}
// @lc code=end

解法 1: 预处理配料组合

function closestCost(baseCosts: number[], toppingCosts: number[], target: number): number {
  let res = -1,
    ans = Infinity
  const set = new Set<number>([0])
  for (let p of toppingCosts) {
    for (let i = 0; i < 2; i++) {
      for (let num of [...set]) {
        set.add(num + p)
      }
    }
  }
  const nums = [...set]
  for (let i = 0; i < baseCosts.length; i++) {
    for (let num of nums) {
      const sum = num + baseCosts[i]
      const d = Math.abs(target - sum)
      if (d < ans || (d === ans && res > sum)) res = sum
      ans = Math.min(ans, d)
    }
  }
  return res
}

Case

test.each([
  { input: { baseCosts: [1, 7], toppingCosts: [3, 4], target: 10 }, output: 10 },
  { input: { baseCosts: [2, 3], toppingCosts: [4, 5, 100], target: 18 }, output: 17 },
  { input: { baseCosts: [3, 10], toppingCosts: [2, 5], target: 9 }, output: 8 },
])(
  'input: baseCosts = $input.baseCosts, toppingCosts = $input.toppingCosts, target = $input.target',
  ({ input: { baseCosts, toppingCosts, target }, output }) => {
    expect(closestCost(baseCosts, toppingCosts, target)).toEqual(output)
  },
)