Closest Dessert Cost
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 lengthn, where eachbaseCosts[i]represents the price of thei^thice cream base flavor.toppingCosts, an integer array of lengthm, where eachtoppingCosts[i]is the price of one of thei^thtopping.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 = 10Output
10Choosing base 1 with cost 7 and one topping of cost 3 gives a total cost of 10.
Example 2
Input
baseCosts = [2,3], toppingCosts = [4,5,100], target = 18Output
17The closest possible total is 17, and it is not possible to make a dessert with total cost 18.
Constraints
- n == baseCosts.length
- m == toppingCosts.length
- 1 <= n, m <= 10
- 1 <= baseCosts[i], toppingCosts[i] <= 10^4
- 1 <= target <= 10^4