【每日一题Day47】LC1774最接近目标价格的甜点成本 | 回溯 哈希表

最接近目标价格的甜点成本【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的长度时（终止条件）
    • 或者当$res==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);
      }
  }
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34

  • 复杂度
    • 时间复杂度：$O(n\ast 3^m)$，$n$为baseCosts的长度，$m$为配料toppingCosts的长度
    • 空间复杂度：$O(m)$，回溯递归的空间开销

动态规划or哈希表

• 思路：由于最终答案可能大于target也可能小于target，可能的范围为$0$至$2\ast 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;
      }
  }
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36

  • 复杂度
    • 时间复杂度：$O(m\ast targe{t}^2)$，$n$为baseCosts的长度，$m$为配料toppingCosts的长度
    • 空间复杂度：$O(target)$，布尔数组的空间开销

• 优化：单独使用变量记录大于target时最小的x数之和$res$，优化空间复杂度和时间复杂度，最后只需在$[target-(res-target),target]$范围内查找是否存在更接近$target$的x数之和即可，从$target$开始向下查找$res-target$个值。

  • 注意：$res$的初始值为大于$target$的底料的最小值，如果不存在可设置为$2\ast 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;
      }
  }
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40