最接近目标价格的甜点成本【LC1744】
You would like to make dessert and are preparing to buy the ingredients. You have n ice cream base flavors and m types of toppings to choose from. You must follow these rules when making your dessert:
- There must be exactly one ice cream base.
- You can add one or more types of topping or have no toppings at all.
- There are at most two of each type of topping.
You are given three inputs:
- baseCosts, an integer array of length n, where each baseCosts[i] represents the price of the ith ice cream base flavor.
- toppingCosts, an integer array of length m, where each toppingCosts[i] is the price of one of the ith topping.
- target, an integer representing your target price for dessert.
You want to make a dessert with a total cost as close to target as possible.
Return the closest possible cost of the dessert to target. If there are multiple, return the lower one.
你打算做甜点，现在需要购买配料。目前共有 n 种冰激凌基料和 m 种配料可供选购。而制作甜点需要遵循以下几条规则：
- 必须选择 一种 冰激凌基料。
- 可以添加 一种或多种 配料，也可以不添加任何配料。
- 每种类型的配料 最多两份 。
给你以下三个输入：
- baseCosts ，一个长度为 n 的整数数组，其中每个 baseCosts[i] 表示第 i 种冰激凌基料的价格。
- toppingCosts，一个长度为 m 的整数数组，其中每个 toppingCosts[i] 表示 一份 第 i 种冰激凌配料的价格。
- target ，一个整数，表示你制作甜点的目标价格。
你希望自己做的甜点总成本尽可能接近目标价格 target 。
返回最接近 target 的甜点成本。如果有多种方案，返回 成本相对较低 的一种。
今天是苦命加班人呀，忙里做题，哈希表的方法明天再写了，继续写本子了=(
哈希表搞定，赶今天的每日一题了（12/05）
首先，明确下题意，可以转化为有限制条件的x个数之和，我们需要返回最接近target的x数之和。
- x数选取的范围是冰淇淋底料baseCosts必须选取一个，配料toppingCosts可以选取数量不限，但是每种配料最多选择两个。
- 由于底料必选一个，因此首先可以找到冰淇淋底料的最小值，如果最小值大于target，那么该值即为最接近target的值，直接返回该值即可。
- 反之，可以使用回溯或者动态规划找到最接近target的x数之和。这里的动态规划，感觉更像是用布尔类型的数组代替了哈希表。
回溯
- 思路：对于每种底料，回溯查找其所有可能的配料组合，返回最接近target的值
- 回溯三部曲
。回溯函数模板返回值以及参数
- toppingCosts（底料数组）
- i（当前选择的元素）
- curCost（当前的总和）
- target（目标和）
- 全局变量：res(最接近target的x数之和)
- 返回值 void
。回溯函数终止条件
- 当curCost已经不可能再对最终结果有影响时，即curCost>target 并且res更加接近target（剪枝1）
- 或者当i大于toppingCosts的长度时（终止条件）
- 或者当r e s = = t a r g e t res==targetres==target时（剪枝2）
。回溯搜索的遍历过程
- 首先判断是否还有可能对结果有影响，若不可能则结束回溯
- 然后判断当前的和是否更接近target，若是则更新res
- 再判断res是否是最接近target的值或者所有配料已经遍历完，是则结束循环
- 若以上情况均不成立，那么继续回溯搜索，对于每种配料都有三种选择：不选、选一个、选两个
class Solution { int res; public int closestCost(int[] baseCosts, int[] toppingCosts, int target) { int minBase = baseCosts[0]; for (int baseCost : baseCosts){ minBase = Math.min(minBase,baseCost); } if (minBase >= target){ return minBase; } res = minBase; for (int baseCost : baseCosts){ backtracking(toppingCosts, 0, baseCost, target); } return res; } public void backtracking(int[] toppingCosts, int i, int curCost, int target){ if (curCost - target > Math.abs(res - target)){ return; } if (Math.abs(curCost - target) < Math.abs(res - target)){ res = curCost; }else if (Math.abs(curCost - target) == Math.abs(res - target)){ res = Math.min(curCost, res); } if (i == toppingCosts.length || res == target){ return; } backtracking(toppingCosts, i + 1, curCost, target); backtracking(toppingCosts, i + 1, curCost + toppingCosts[i], target); backtracking(toppingCosts, i + 1, curCost + toppingCosts[i] * 2, target); } }
。复杂度
- 时间复杂度：O(n∗3 m )，n 为baseCosts的长度，m 为配料toppingCosts的长度
- 空间复杂度：O(m)，回溯递归的空间开销
动态规划or哈希表
- 思路：由于最终答案可能大于target也可能小于target，可能的范围为0 至2∗target。因此，可以使用一个布尔类型的数组flag，数组长度为2*target+1，记录可能出现的x数之和，最后返回最接近target的x数之和即可
- 实现：
。首先处理特殊情况
- 存在冰淇淋底料等于target，直接返回target
- 冰淇淋底料的最小值大于target，直接返回冰淇淋底料的最小值
。然后选定一个冰淇淋底料：遍历数组baseCosts，将flag[baseCost]设置为true
。然后为每个冰淇淋底料添加同一配料的一个或者两个：更新可能的x数之和
- 注意：为了避免重复添加配料，需要倒序遍历flag数组
。最后以target为中心，返回最接近target的x数之和
class Solution { int res; public int closestCost(int[] baseCosts, int[] toppingCosts, int target) { int minBase = baseCosts[0]; boolean[] flag = new boolean[target * 2 + 1]; for (int baseCost : baseCosts){ if (baseCost == target){ return target; }else if (baseCost < 2 * target){ flag[baseCost] = true; } minBase = Math.min(minBase,baseCost); } if (minBase >= target){ return minBase; } for (int toppingCost : toppingCosts){ for (int count = 0; count <= 1; count++){ for (int i = 2 * target; i >= 0; i--){ if (i - toppingCost >= 0){ flag[i] = flag[i] | flag[i - toppingCost]; } } } } for (int i = 0; i <= target; i++){ if (flag[target - i]){ return target - i; }else if (flag[target + i]){ return target + i; } } return 0; } }
。复杂度
- 时间复杂度：O ( m ∗ t a r g e t 2 )，n 为baseCosts的长度，m 为配料toppingCosts的长度
- 空间复杂度：O(target)，布尔数组的空间开销
- 优化：单独使用变量记录大于target时最小的x数之和res，优化空间复杂度和时间复杂度，最后只需在[target−(res−target),target]范围内查找是否存在更接近target的x数之和即可，从target开始向下查找res−target个值。
。注意：res的初始值为大于target的底料的最小值，如果不存在可设置为2∗target−minBase，因为大于该和与目标和target的距离一定大于仅选最小底料的情况，所以一定不会是最优解。
class Solution { public int closestCost(int[] baseCosts, int[] toppingCosts, int target) { int minBase = baseCosts[0]; boolean[] flag = new boolean[target + 1]; int res = Integer.MAX_VALUE; for (int baseCost : baseCosts){ if (baseCost == target){ return target; }else if (baseCost > target){ res = Math.min(res,baseCost); }else if (baseCost < target){ flag[baseCost] = true; } minBase = Math.min(minBase,baseCost); } if (minBase >= target){ return minBase; } res = Math.min(res,2 * target - minBase); for (int toppingCost : toppingCosts){ for (int count = 0; count <= 1; count++){ for (int i = target; i >= 0; i--){ if (flag[i] && i + toppingCost > target){ res = Math.min(res, i + toppingCost); } if (i - toppingCost >= 0){ flag[i] = flag[i] | flag[i - toppingCost]; } } } } for (int i = 0 ; i <= res - target; i++){ if (flag[target - i]){ return target - i; } } return res; } }
