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 theith
ice cream base flavor.toppingCosts
, an integer array of lengthm
, where eachtoppingCosts[i]
is the price of one of theith
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.
Example 4:
Input: baseCosts = [10], toppingCosts = [1], target = 1 Output: 10 Explanation: Notice that you don't have to have any toppings, but you must have exactly one base.
Constraints:
n == baseCosts.length
m == toppingCosts.length
1 <= n, m <= 10
1 <= baseCosts[i], toppingCosts[i] <= 104
1 <= target <= 104
Solution: DP / Knapsack
Pre-compute the costs of all possible combinations of toppings.
Time complexity: O(sum(toppings) * 2 * (m + n)) ~ O(10^6)
Space complexity: O(sum(toppings)) ~ O(10^5)
C++
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 |
// Author: Huahua class Solution { public: int closestCost(vector<int>& bs, vector<int>& ts, int target) { const int kMax = 2 * accumulate(begin(ts), end(ts), 0); int min_diff = INT_MAX; int ans = INT_MAX; vector<int> dp(kMax + 1); dp[0] = 1; for (int t : ts) { for (int i = kMax; i >= 0; --i) { if (!dp[i]) continue; if (i + t <= kMax) dp[i + t] = 1; if (i + 2 * t <= kMax) dp[i + 2 * t] = 1; } } for (int i = 0; i <= kMax; ++i) { if (!dp[i]) continue; for (int b : bs) { const int diff = abs(b + i - target); if (diff < min_diff || diff == min_diff && b + i < ans) { min_diff = diff; ans = b + i; } } } return ans; } }; |
Solution 2: DFS
Combination
Time complexity: O(3^m * n)
Space complexity: O(m)
C++
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 |
// Author: Huahua class Solution { public: int closestCost(vector<int>& bs, vector<int>& ts, int target) { const int m = ts.size(); int min_diff = INT_MAX; int ans = INT_MAX; function<void(int, int)> dfs = [&](int s, int cur) { if (s == m) { for (int b : bs) { const int total = b + cur; const int diff = abs(total - target); if (diff < min_diff || diff == min_diff && total < ans) { min_diff = diff; ans = total; } } return; } for (int i = s; i < m; ++i) { dfs(i + 1, cur); dfs(i + 1, cur + ts[i]); dfs(i + 1, cur + ts[i] * 2); } }; dfs(0, 0); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment