Question

1774. Closest Dessert Cost

中文文档

Description

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._

 

Example 1:

Input: baseCosts = [1,7], toppingCosts = [3,4], target = 10
Output: 10
Explanation: Consider the following combination (all 0-indexed):
- Choose base 1: cost 7
- Take 1 of topping 0: cost 1 x 3 = 3
- Take 0 of topping 1: cost 0 x 4 = 0
Total: 7 + 3 + 0 = 10.

Example 2:

Input: baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
Output: 17
Explanation: Consider the following combination (all 0-indexed):
- Choose base 1: cost 3
- Take 1 of topping 0: cost 1 x 4 = 4
- Take 2 of topping 1: cost 2 x 5 = 10
- Take 0 of topping 2: cost 0 x 100 = 0
Total: 3 + 4 + 10 + 0 = 17. You cannot make a dessert with a total cost of 18.

Example 3:

Input: baseCosts = [3,10], toppingCosts = [2,5], target = 9
Output: 8
Explanation: It is possible to make desserts with cost 8 and 10. Return 8 as it is the lower cost.

 

Constraints:

• n == baseCosts.length
• m == toppingCosts.length
• 1 <= n, m <= 10
• 1 <= baseCosts[i], toppingCosts[i] <= 104
• 1 <= target <= 104

Solutions

Solution 1

class Solution:
  def closestCost(
    self, baseCosts: List[int], toppingCosts: List[int], target: int
  ) -> int:
    def dfs(i, t):
      if i >= len(toppingCosts):
        arr.append(t)
        return
      dfs(i + 1, t)
      dfs(i + 1, t + toppingCosts[i])

    arr = []
    dfs(0, 0)
    arr.sort()
    d = ans = inf

    # 选择一种冰激淋基料
    for x in baseCosts:
      # 枚举子集和
      for y in arr:
        # 二分查找
        i = bisect_left(arr, target - x - y)
        for j in (i, i - 1):
          if 0 <= j < len(arr):
            t = abs(x + y + arr[j] - target)
            if d > t or (d == t and ans > x + y + arr[j]):
              d = t
              ans = x + y + arr[j]
    return ans

class Solution {
  private List<Integer> arr = new ArrayList<>();
  private int[] ts;
  private int inf = 1 << 30;

  public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
    ts = toppingCosts;
    dfs(0, 0);
    Collections.sort(arr);
    int d = inf, ans = inf;

    // 选择一种冰激淋基料
    for (int x : baseCosts) {
      // 枚举子集和
      for (int y : arr) {
        // 二分查找
        int i = search(target - x - y);
        for (int j : new int[] {i, i - 1}) {
          if (j >= 0 && j < arr.size()) {
            int t = Math.abs(x + y + arr.get(j) - target);
            if (d > t || (d == t && ans > x + y + arr.get(j))) {
              d = t;
              ans = x + y + arr.get(j);
            }
          }
        }
      }
    }
    return ans;
  }

  private int search(int x) {
    int left = 0, right = arr.size();
    while (left < right) {
      int mid = (left + right) >> 1;
      if (arr.get(mid) >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }

  private void dfs(int i, int t) {
    if (i >= ts.length) {
      arr.add(t);
      return;
    }
    dfs(i + 1, t);
    dfs(i + 1, t + ts[i]);
  }
}

class Solution {
public:
  const int inf = INT_MAX;
  int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
    vector<int> arr;
    function<void(int, int)> dfs = [&](int i, int t) {
      if (i >= toppingCosts.size()) {
        arr.push_back(t);
        return;
      }
      dfs(i + 1, t);
      dfs(i + 1, t + toppingCosts[i]);
    };
    dfs(0, 0);
    sort(arr.begin(), arr.end());
    int d = inf, ans = inf;
    // 选择一种冰激淋基料
    for (int x : baseCosts) {
      // 枚举子集和
      for (int y : arr) {
        // 二分查找
        int i = lower_bound(arr.begin(), arr.end(), target - x - y) - arr.begin();
        for (int j = i - 1; j < i + 1; ++j) {
          if (j >= 0 && j < arr.size()) {
            int t = abs(x + y + arr[j] - target);
            if (d > t || (d == t && ans > x + y + arr[j])) {
              d = t;
              ans = x + y + arr[j];
            }
          }
        }
      }
    }
    return ans;
  }
};

func closestCost(baseCosts []int, toppingCosts []int, target int) int {
  arr := []int{}
  var dfs func(int, int)
  dfs = func(i, t int) {
    if i >= len(toppingCosts) {
      arr = append(arr, t)
      return
    }
    dfs(i+1, t)
    dfs(i+1, t+toppingCosts[i])
  }
  dfs(0, 0)
  sort.Ints(arr)
  const inf = 1 << 30
  ans, d := inf, inf
  // 选择一种冰激淋基料
  for _, x := range baseCosts {
    // 枚举子集和
    for _, y := range arr {
      // 二分查找
      i := sort.SearchInts(arr, target-x-y)
      for j := i - 1; j < i+1; j++ {
        if j >= 0 && j < len(arr) {
          t := abs(x + y + arr[j] - target)
          if d > t || (d == t && ans > x+y+arr[j]) {
            d = t
            ans = x + y + arr[j]
          }
        }
      }
    }
  }
  return ans
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}

const closestCost = function (baseCosts, toppingCosts, target) {
  let closestDessertCost = -Infinity;
  function dfs(dessertCost, j) {
    const tarCurrDiff = Math.abs(target - dessertCost);
    const tarCloseDiff = Math.abs(target - closestDessertCost);
    if (tarCurrDiff < tarCloseDiff) {
      closestDessertCost = dessertCost;
    } else if (tarCurrDiff === tarCloseDiff && dessertCost < closestDessertCost) {
      closestDessertCost = dessertCost;
    }
    if (dessertCost > target) return;
    if (j === toppingCosts.length) return;
    for (let count = 0; count <= 2; count++) {
      dfs(dessertCost + count * toppingCosts[j], j + 1);
    }
  }
  for (let i = 0; i < baseCosts.length; i++) {
    dfs(baseCosts[i], 0);
  }
  return closestDessertCost;
};