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

题目描述

思路及实现

深度优先搜索

对于深度优先搜索做法的话，就没什么好说的了，就是枚举所有情况然后找个最符合题意的结果返回就是了。

class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
        ans_list = set()  # 记录所有成本
        ans = math.inf
        def dfs(depth: int, cur_cost: int) -> None:
            nonlocal ans_list
            ans_list.add(cur_cost)
            if depth == len(toppingCosts):  # 深度搜索完毕
                return
            dfs(depth + 1, cur_cost + 2 * toppingCosts[depth])  # 添加两份当前配料
            dfs(depth + 1, cur_cost + toppingCosts[depth])  # 添加一份当前配料
            dfs(depth + 1, cur_cost)  # 不添加当前配料
        for base_cost in baseCosts:  # 进行深度优先搜索
            dfs(0, base_cost)
        for cost in ans_list:  # 找到最小成本
            if abs(cost - target) < abs(ans - target):  # 当前成本差距小于记录的成本差距，直接更新
                ans = cost
            elif abs(cost - target) == abs(ans - target):  # 当前成本差距等于记录的成本差距，取更小成本
                if cost < ans:
                    ans = cost
        return ans

当然，为了避免没有必要的搜索，可以进行剪枝。

class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
        ans = min(baseCosts)
        # 注意“成本差距”和“成本”两个概念
        def dfs(depth: int, cur_cost: int) -> None:
            nonlocal ans
            if abs(ans - target) < cur_cost - target:  # 如果当前成本差距已经大于记录的成本差距，直接返回，因为继续搜索只会增加成本(注意，当前成本差值不取绝对值才能保证)
                return
            if abs(ans - target) >= abs(cur_cost - target):
                if abs(ans - target) > abs(cur_cost - target):  # 如果当前成本差距小于记录的成本差距
                    ans = cur_cost  # 就更新最小成本差距
                else:  # 如果当前成本差距等于记录的成本差距
                    ans = min(ans, cur_cost)  # 记录更小的成本
            if depth == len(toppingCosts):  # 深度搜索完毕
                return
            dfs(depth + 1, cur_cost + 2 * toppingCosts[depth])  # 添加两份当前配料
            dfs(depth + 1, cur_cost + toppingCosts[depth])  # 添加一份当前配料
            dfs(depth + 1, cur_cost)  # 不添加当前配料
        for base_cost in baseCosts:
            dfs(0, base_cost)
        return ans

动态规划

本题属于是01背包问题的变种，在这题里边，存在一定要放入且只能放入一个的基料，还有可放入可不放入的辅料，所以可以把辅料看作是背包问题中的物品，而这个物品（辅料）是可以放两次的，在背包问题中只能放一次，而且，对于这题，需要考虑如何处理大于target的部分，因为在01背包问题中，总物品重量是不能超过背包可承载重量的，但是这里制作成本可以超过目标制造成本，因为我们考虑的是更小的成本差距。
那就需要对于这些不同的部分进行处理了，我们来一步一步处理：

1. 在这里，我们是通过01背包问题的方式来求对于一个成本cost，我们是否能够找到一个构造方案。最后再找到距离target最近的可构造的成本方案。
2. 题目有一个隐藏上限：即成本差距最大就是(target - min(baseCosts))，大于此成本差距的制作方法一定不是最优解。
3. 首先对于放入的基料而言，如果处理？对于小于target的基料，我们就尝试往上面添加辅料，即把它们作为动态规划数组的初始状态；对于大于target的基料，根据第1点提到过的上限，我们可以知道如果基料成本大于2 * target - min(baseCosts)的话一定不是最优解，小于的话，就用它更新最小成本。
4. 对于一种辅料最多放两份，那就每种辅料都处理两次，即进行两次循环。
5. 如何添加辅料？对于一种方案cost，我们设i为第i种辅料，那么有dp[cost] = dp[cost - toppingCosts[i]] | dp[cost]。

   class Solution:
       def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
           cost = min(baseCosts)
           if cost >= target:
               return cost
           ans = 2 * target - cost
           dp = [False] * (target + 1)
           for c in baseCosts:
               if c == target:
                   return c
               if c > target:
                   ans = min(ans, c)
               else:
                   dp[c] = True
           for i in toppingCosts:
               for _ in range(2):
                   for c in range(target, 0, -1):
                       if dp[c] and c + i > target:  # 在这题中要额外处理一种成本方案加入辅料后大于target的情况
                           ans = min(ans, c + i)
                       if c > i:  # 01背包构造成本方案
                           dp[c] |= dp[c - i]
           for i in range(ans - target + 1):
               if dp[target - i]:
                   return target - i
           return ans

其他话（关于背包DP）

没想到吧，这么经典的题我也是第一次了解，之前只听过没写过。
首先是放一下学习的地方嗷：背包DP
这里主要是写一些我在看这个问题时候的疑惑以及解释。

第一个疑惑：错误的核心代码里边写的什么？l从0到W - w[i]是啥意思啊？

还有一点需要注意的是，很容易写出这样的错误核心代码：

# Python Version
for i in range(1, n + 1):
    l = 0
    while l <= W - w[i]:
        f[l + w[i]] = max(f[l] + v[i], f[l + w[i]])
        l += 1
# 由 f[i][l + w[i]] = max(max(f[i - 1][l + w[i]],f[i - 1][l] + w[i]),f[i][l + w[i]]) 简化而来

OK，那么要明白对于背包问题中f[i][j]是什么，f[i][j]就是只放前i（包括第i个）个物品时，背包重量为j的时候，背包中物品的最大价值。
那么现在能够看出，这里在求从f[i][0 + w[i]]开始，一直到f[i][l + w[i]]（为什么是这个数呢？因为不能超过背包可承载的重量W），计算f[0 + w[i]]至f[l + w[i]]每一个重量下所能达到的最大总价值。
为什么这里错了呢？因为f[i][j]会受到f[i][j - w[i]]的影响，这又是什么意思呢？意思是我们并不知道f[i][j - w[i]]这种情况下是否是在i被塞入的时候计算得出的，如果是，而且f[i][j]还更新为f[i][j - w[i]]的值的话，那就相当于把这个物品塞入多次，不符合题意了。
举个例子，现在有l = 2， w[i] = 4，那么会有：f[2 + 4] = max(f[2] + v[i], f[2 + 4])，而对于在这之后可能出现的情况l = 6， w[i] = 4，又有：f[6 + 4] = max(f[6] + v[i], f[6 + 4])，而这其中出现的f[6]，怎么保证不是我们之前在求f[2 + 4]的时候取的f[2] + v[i]的值呢？如果是的话，那物品i不就相当于放入多次了吗？
所以，为了避免出现这种情况，我们选择了从l = W开始枚举而不是从l = 0开始。

for i in range(1, n + 1):
	for l in range(W, w[i], -1):
		f[l] = max(f[l], f[l - w[i]] + v[i])

这样，我们就能保证f[i][j]总是在f[i][j - w[i]]之前更新了。
至此，01背包问题就解决完毕了。

---

希望本文章能够帮到您~