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

标签: 数组 动态规划 回溯

难度: 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

Submission

运行时间: 64 ms

内存: 16.5 MB

class Solution:
    def closestCost(
        self, baseCosts: List[int], toppingCosts: List[int], target: int
    ) -> int:
        """
        每种类型的配料最多可以选两份，因此，我们可以复制一份配料，
        然后利用 DFS 枚举子集之和。在实现上，我们可以只枚举一半的配料的所有子集和，
        然后在另一半配料子集和中，利用二分查找找到最接近的配料。
        """

        def dfs(i, s):
            if i < 0:
                arr.append(s)
                return
            dfs(i - 1, s)
            dfs(i - 1, s + toppingCosts[i])

        arr = []
        n = len(toppingCosts)
        dfs(n - 1, 0)
        arr.sort()
        m = len(arr)
        ans = diff = inf

        for base in baseCosts:
            for x in arr:
                # x + ? + base >= target
                # ? >= target - x - base
                i = bisect_left(arr, target - x - base)
                for j in i, i - 1:
                    if 0 <= j < m:
                        cost = x + base + arr[j]
                        d = abs(cost - target)
                        if d < diff or (d == diff and cost < ans):
                            ans, diff = cost, d
        return ans

Explain

此问题的解决方案使用深度优先搜索（DFS）来生成所有可能的配料组合的成本，并以此来找出最接近目标价的甜点成本。首先，对于配料成本，我们可以考虑每种配料最多两份，因此可以将每份配料复制一份，从而将问题转化为选择或不选择配料的问题。使用DFS遍历所有可能的配料成本组合，并将结果存储在数组中。对于每一种基础成本，我们结合配料成本，使用二分查找（由于数组是有序的）来寻找最接近目标成本的组合。如果找到多个相同距离的成本，则选择成本较低的一个。

时间复杂度: O(n * 3^m * log(3^m))

空间复杂度: O(3^m)

class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
        def dfs(i, s):
            # 递归生成所有可能的配料组合成本
            if i < 0:
                arr.append(s)
                return
            dfs(i - 1, s)  # 不添加当前配料
            dfs(i - 1, s + toppingCosts[i])  # 添加一份当前配料

        arr = []  # 存储所有可能的配料组合成本
        n = len(toppingCosts)
        dfs(n - 1, 0)  # 从最后一个配料开始递归
        arr.sort()  # 排序以便后续二分查找
        m = len(arr)
        ans = diff = inf  # 初始化答案和最小差值

        for base in baseCosts:  # 遍历每种基础成本
            for x in arr:  # 遍历每种配料组合成本
                i = bisect_left(arr, target - x - base)  # 二分查找最接近目标的成本
                for j in i, i - 1:  # 检查最接近的两个位置
                    if 0 <= j < m:
                        cost = x + base + arr[j]  # 计算总成本
                        d = abs(cost - target)  # 计算与目标的差值
                        if d < diff or (d == diff and cost < ans):
                            ans, diff = cost, d  # 更新答案
        return ans

Explore

在提供的问题中，每种配料可以选择不添加、添加一份或添加两份。这种方法确保了所有可能的成本组合都被考虑到，因为对于每种配料，我们都探索了其所有可能的贡献（即0份、1份或2份）。通过递归地应用这一逻辑，深度优先搜索（DFS）能够遍历生成所有从不添加任何配料到添加每种配料两份的所有可能的成本组合。因此，这种分类方法确保了在配料的选择上没有遗漏任何潜在的成本计算，从而可以精确地计算出接近目标价格的甜点成本。

将配料成本的数组`arr`进行排序后使用二分查找是为了提高查找效率。如果直接遍历数组来找到最接近目标的成本组合，时间复杂度为O(n)，其中n是数组`arr`的长度。但通过首先排序数组，然后使用二分查找，我们可以将查找最接近值的时间复杂度降低到O(log n)。这样做特别在数组长度较大时更有效率。排序确保了数组是有序的，这是二分查找算法的前提条件，因为二分查找通过比较中间元素与目标值来决定搜索的方向，这一过程依赖于数组的有序性。

`bisect_left`方法是一个在有序列表中进行二分查找的函数，它返回插入点以维持列表的排序顺序，即它找到第一个不小于目标值的元素的位置。在本问题中，这意味着`bisect_left`可以帮助我们快速找到不小于目标成本（调整后的目标值减去基础成本和当前配料成本的差值）的第一个成本值，在这个基准上我们可以比较最近的两个成本（当前位置和前一个位置），以确定哪个更接近目标成本。使用`bisect_left`能够有效地缩小搜索范围并快速定位，从而提高整体的查找效率。