【2022-12-04每日一题】1774. 最接近目标价格的甜点成本[Medium]

2022-12-04每日一题：1774. 最接近目标价格的甜点成本

难度：Medium

标签：数组 、 动态规划 、 回溯

你打算做甜点，现在需要购买配料。目前共有 n 种冰激凌基料和 m 种配料可供选购。而制作甜点需要遵循以下几条规则：

• 必须选择 一种 冰激凌基料。
• 可以添加 一种或多种 配料，也可以不添加任何配料。
• 每种类型的配料 最多两份 。

给你以下三个输入：

• baseCosts ，一个长度为 n 的整数数组，其中每个 baseCosts[i] 表示第 i 种冰激凌基料的价格。
• toppingCosts，一个长度为 m 的整数数组，其中每个 toppingCosts[i] 表示 一份 第 i 种冰激凌配料的价格。
• target ，一个整数，表示你制作甜点的目标价格。

你希望自己做的甜点总成本尽可能接近目标价格 target 。

返回最接近 target 的甜点成本。如果有多种方案，返回 成本相对较低 的一种。

示例 1：

输入：baseCosts = [1,7], toppingCosts = [3,4], target = 10
输出：10
解释：考虑下面的方案组合（所有下标均从 0 开始）：
- 选择 1 号基料：成本 7
- 选择 1 份 0 号配料：成本 1 x 3 = 3
- 选择 0 份 1 号配料：成本 0 x 4 = 0
总成本：7 + 3 + 0 = 10 。

示例 2：

输入：baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
输出：17
解释：考虑下面的方案组合（所有下标均从 0 开始）：
- 选择 1 号基料：成本 3
- 选择 1 份 0 号配料：成本 1 x 4 = 4
- 选择 2 份 1 号配料：成本 2 x 5 = 10
- 选择 0 份 2 号配料：成本 0 x 100 = 0
总成本：3 + 4 + 10 + 0 = 17 。不存在总成本为 18 的甜点制作方案。

示例 3：

输入：baseCosts = [3,10], toppingCosts = [2,5], target = 9
输出：8
解释：可以制作总成本为 8 和 10 的甜点。返回 8 ，因为这是成本更低的方案。

示例 4：

输入：baseCosts = [10], toppingCosts = [1], target = 1
输出：10
解释：注意，你可以选择不添加任何配料，但你必须选择一种基料。

提示：

• n == baseCosts.length
• m == toppingCosts.length
• 1 <= n, m <= 10
• 1 <= baseCosts[i], toppingCosts[i] <= 104
• 1 <= target <= 104

方法一：枚举子集和 + 排序 + 二分查找

• 相关题解-ylb

每种类型的配料最多可以选两份，因此，我们可以复制一份配料，然后利用 DFS 枚举子集之和。在实现上，我们可以只枚举一半的配料的所有子集和，然后在另一半配料子集和中，利用二分查找找到最接近的配料。

func closestCost(baseCosts []int, toppingCosts []int, target int) int {
    arr := []int{}
    var dfs func(int, int)
    dfs = func(i, t int) {
        if i >= len(toppingCosts) {
            arr = append(arr, t)
            return
        }
        dfs(i+1, t) // 不选当前配料
        dfs(i+1, t+toppingCosts[i]) // 选当前配料
    }
    dfs(0, 0)
    sort.Ints(arr)
    const inf = 1 << 30
    ans, d := inf, inf
    // 选择一种冰淇淋基料
    for _, x := range baseCosts {
        // 枚举子集合
        for _, y := range arr {
            // 二分查找
            i := sort.Search(len(arr), func (i int) bool { return arr[i] >= target-x-y })
            for j := i-1; j < i+1; j++ {
                if j >= 0 && j < len(arr) {
                    t := abs(x+y+arr[j]-target)
                    if d > t || (d == t && ans > x+y+arr[j]) {
                        d = t
                        ans = x+y+arr[j]
                    }
                }
            }
        }
    }
    return ans
}

func abs(a int) int {
    if a > 0 {
        return a
    }
    return -a
}

复杂度分析

• 时间复杂度: O(n×2^m×log2^m)。其中 m 是配料种类，而 n 是冰激淋基料种类。

方法二：回溯

• 相关题解

详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读

func closestCost(baseCosts []int, toppingCosts []int, target int) int {
    ans := baseCosts[0]
    for _, c := range baseCosts {
        ans = min(ans, c)
    }
    var dfs func(int,int)
    dfs = func (p, curCost int) {
        if abs(ans-target) < curCost-target {
            return
        } else if abs(ans-target) >= abs(curCost-target) {
            if abs(ans-target) > abs(curCost-target) {
                ans = curCost
            } else {
                ans = min(ans, curCost)
            }
        }
        if p == len(toppingCosts) {
            return
        }
        dfs(p+1, curCost)
        dfs(p+1, curCost+toppingCosts[p])
        dfs(p+1, curCost+toppingCosts[p]*2)
    }
    for _, c := range baseCosts {
        dfs(0, c)
    }
    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

复杂度分析

• 时间复杂度：O(n×3^m) ，其中 n，m 分别为数组 baseCosts，toppingCosts 的长度。

• 空间复杂度：O(m)，主要为回溯递归的空间开销。

方法三：动态规划

详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读

func closestCost(baseCosts []int, toppingCosts []int, target int) int {
    x := baseCosts[0]
    for _, c := range baseCosts {
        x = min(x, c)
    }
    if x > target {
        return x
    }
    can := make([]bool, target+1)
    ans := 2*target - x
    for _, c := range baseCosts {
        if c <= target {
            can[c] = true
        } else {
            ans = min(ans, c)
        }
    }
    for _, c := range toppingCosts {
        for count := 0; count < 2; count++ {
            for i := target; i > 0; i-- {
                if can[i] && i+c > target {
                    ans = min(ans, i+c)
                }
                if i-c > 0 {
                    can[i] = can[i] || can[i-c]
                }
            }
        }
    }
    for i := 0; i <= ans-target; i++ {
        if can[target-i] {
            return target - i
        }
    }
    return ans
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

复杂度分析

• 时间复杂度：O(target×m)，其中 m 为数组 toppingCosts 的长度，target 为目标值。动态规划的时间复杂度是 O(MAXC×m)，由于 MAXC=target，因此时间复杂度是 O(target×m)。
• 空间复杂度：O(target)，其中 target 为目标值。需要创建长度为 target+1 的数组 can。

LeetCode题库地址

• https://leetcode.cn/problems/closest-dessert-cost