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

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

解法一

baseCosts基料必选，toppingCosts配料不定数量，因此考虑用dfs搜索toppingCosts

class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
        self.res= sys.maxsize
        self.minDis = sys.maxsize
        self.list= []

        n = len(baseCosts)
        m = len(toppingCosts)
        
        def dfs(i, j, cost):
            if i >=n or j >= m :  #递归出口（这里不能用cost > target条件剪枝
                return
            
            #第j种选k=0~2份
            for k in range(3):
                # 用tmp计算当前cost，不修改cost以保存现场
                tmp = cost + toppingCosts[j]*k
                #找到比res更接近target的数
                if abs(tmp - target) <= abs(self.res - target):
                    #记录下来每个接近target的数
                    #【重点】写入list
                    self.res = tmp
                    self.minDis = abs(tmp - target)
                    self.list.append(tmp)
                dfs(i, j+1, tmp)	#dfs下一种配料

        for i in  range(n):
            dfs(i, 0, baseCosts[i])	#基料必选，因此遍历基料，对每种配料dfs
        #注意求的是【最接近】target的数中，【最小】的。
        #因此还要再次筛选
        #由于【最接近】的距离已经确定，因此只需要在【最接近】的限定范围中找【最小】的
        finalRes=sys.maxsize
        for i in self.list:
            if abs(i - target) <= self.minDis and i < finalRes:
                finalRes = i
        return finalRes      

gpt4的回答

首先我们需要理解题目要求的问题，题目要求在给定冰激凌基料、配料价格和目标价格情况下，寻找一种计算出的总成本接近目标价格的甜点配料方案。这里需要用到一些遍历和回溯的思路，思路如下：

1. 定义一个全局变量 res 用于存放最接近目标价格的总成本，初始化为最大值。

2. 将 toppingCosts 变量的数组进行排序，方便之后进行计算。

3. 遍历所有的冰激凌基料，然后递归遍历所有的配料组合。

4. 在递归过程中，需要添加当前选择的配料数量（从 0 到 2）计算当前方案的成本，然后回溯换下一个配料组合。

5. 检查当前方案的成本是否比之前的更接近目标价格，然后更新 res 值。

6. 最终返回 res 变量即可。

下面是这个思路的 Python 实现：

class Solution:
    def closestCost(self,baseCosts, toppingCosts, target):
        def dfs(i, cur_cost):
            # 更新最接近目标价格的方案
            nonlocal res
            if abs(cur_cost - target) < abs(res - target) or (abs(cur_cost - target) == abs(res - target) and cur_cost < res):
                res = cur_cost
            # 达到最后一个配料
            if i == len(toppingCosts):
                return
            # 尝试添加不同数量的配料
            for j in range(3):
                dfs(i + 1, cur_cost + j * toppingCosts[i])

        res = float('inf')
        toppingCosts.sort()
        for cost in baseCosts:
            dfs(0, cost)
        return res

这个实现解决了题目的问题并通过了示例测试。其时间复杂度为 O(n * m^3)，因为我们需要遍历所有的基料（n 种）和配料组合方案（m * 3）。