{"id":8164,"date":"2021-02-27T20:48:52","date_gmt":"2021-02-28T04:48:52","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8164"},"modified":"2021-02-27T21:20:54","modified_gmt":"2021-02-28T05:20:54","slug":"leetcode-1774-closest-dessert-cost","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1774-closest-dessert-cost\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1774. Closest Dessert Cost"},"content":{"rendered":"\n<p>You would like to make dessert and are preparing to buy the ingredients. You have&nbsp;<code>n<\/code>&nbsp;ice cream base flavors and&nbsp;<code>m<\/code>&nbsp;types of toppings to choose from. You must follow these rules when making your dessert:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>There must be&nbsp;<strong>exactly one<\/strong>&nbsp;ice cream base.<\/li><li>You can add&nbsp;<strong>one or more<\/strong>&nbsp;types of topping or have no toppings at all.<\/li><li>There are&nbsp;<strong>at most two<\/strong>&nbsp;of&nbsp;<strong>each type<\/strong>&nbsp;of topping.<\/li><\/ul>\n\n\n\n<p>You are given three inputs:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>baseCosts<\/code>, an integer array of length&nbsp;<code>n<\/code>, where each&nbsp;<code>baseCosts[i]<\/code>&nbsp;represents the price of the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;ice cream base flavor.<\/li><li><code>toppingCosts<\/code>, an integer array of length&nbsp;<code>m<\/code>, where each&nbsp;<code>toppingCosts[i]<\/code>&nbsp;is the price of&nbsp;<strong>one<\/strong>&nbsp;of the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;topping.<\/li><li><code>target<\/code>, an integer representing your target price for dessert.<\/li><\/ul>\n\n\n\n<p>You want to make a dessert with a total cost as close to&nbsp;<code>target<\/code>&nbsp;as possible.<\/p>\n\n\n\n<p>Return&nbsp;<em>the closest possible cost of the dessert to&nbsp;<\/em><code>target<\/code>. If there are multiple, return&nbsp;<em>the&nbsp;<strong>lower<\/strong>&nbsp;one.<\/em><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> baseCosts = [1,7], toppingCosts = [3,4], target = 10\n<strong>Output:<\/strong> 10\n<strong>Explanation:<\/strong> Consider the following combination (all 0-indexed):\n- Choose base 1: cost 7\n- Take 1 of topping 0: cost 1 x 3 = 3\n- Take 0 of topping 1: cost 0 x 4 = 0\nTotal: 7 + 3 + 0 = 10.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> baseCosts = [2,3], toppingCosts = [4,5,100], target = 18\n<strong>Output:<\/strong> 17\n<strong>Explanation:<\/strong> Consider the following combination (all 0-indexed):\n- Choose base 1: cost 3\n- Take 1 of topping 0: cost 1 x 4 = 4\n- Take 2 of topping 1: cost 2 x 5 = 10\n- Take 0 of topping 2: cost 0 x 100 = 0\nTotal: 3 + 4 + 10 + 0 = 17. You cannot make a dessert with a total cost of 18.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> baseCosts = [3,10], toppingCosts = [2,5], target = 9\n<strong>Output:<\/strong> 8\n<strong>Explanation:<\/strong> It is possible to make desserts with cost 8 and 10. Return 8 as it is the lower cost.\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> baseCosts = [10], toppingCosts = [1], target = 1\n<strong>Output:<\/strong> 10\n<strong>Explanation:<\/strong> Notice that you don't have to have any toppings, but you must have exactly one base.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>n == baseCosts.length<\/code><\/li><li><code>m == toppingCosts.length<\/code><\/li><li><code>1 &lt;= n, m &lt;= 10<\/code><\/li><li><code>1 &lt;= baseCosts[i], toppingCosts[i] &lt;= 10<sup>4<\/sup><\/code><\/li><li><code>1 &lt;= target &lt;= 10<sup>4<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong> \/ <strong>Knapsack<\/strong> <\/h2>\n\n\n\n<p>Pre-compute the costs of all possible combinations of toppings.<\/p>\n\n\n\n<p>Time complexity: O(sum(toppings) * 2 * (m + n)) ~ O(10^6)<br>Space  complexity: O(sum(toppings)) ~ O(10^5)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int closestCost(vector<int>& bs, vector<int>& ts, int target) {\n    const int kMax = 2 * accumulate(begin(ts), end(ts), 0);\n    int min_diff = INT_MAX;\n    int ans = INT_MAX;\n    vector<int> dp(kMax + 1);\n    dp[0] = 1;\n    for (int t : ts) {\n      for (int i = kMax; i >= 0; --i) {\n        if (!dp[i]) continue;\n        if (i + t <= kMax) dp[i + t] = 1;\n        if (i + 2 * t <= kMax) dp[i + 2 * t] = 1;        \n      }\n    }   \n    for (int i = 0; i <= kMax; ++i) {\n      if (!dp[i]) continue;\n       for (int b : bs) {\n        const int diff = abs(b + i - target);\n        if (diff < min_diff || diff == min_diff &#038;&#038; b + i < ans) {\n          min_diff = diff;\n          ans = b + i;\n        }\n      }\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: DFS<\/strong><\/h2>\n\n\n\n<p>Combination<\/p>\n\n\n\n<p>Time complexity: O(3^m * n)<br>Space complexity: O(m)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int closestCost(vector<int>& bs, vector<int>& ts, int target) {\n    const int m = ts.size();\n    int min_diff = INT_MAX;\n    int ans = INT_MAX;\n    function<void(int, int)> dfs = [&](int s, int cur) {\n      if (s == m) {\n        for (int b : bs) {\n          const int total = b + cur;\n          const int diff = abs(total - target);\n          if (diff < min_diff \n              || diff == min_diff &#038;&#038; total < ans) {\n            min_diff = diff;\n            ans = total;\n          }\n        }\n        return;\n      }      \n      for (int i = s; i < m; ++i) {\n        dfs(i + 1, cur);\n        dfs(i + 1, cur + ts[i]);\n        dfs(i + 1, cur + ts[i] * 2);\n      }\n    };    \n    dfs(0, 0);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You would like to make dessert and are preparing to buy the ingredients. You have&nbsp;n&nbsp;ice cream base flavors and&nbsp;m&nbsp;types of toppings to choose from. You&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[33,18,177,42],"class_list":["post-8164","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dfs","tag-dp","tag-medium","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8164","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8164"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8164\/revisions"}],"predecessor-version":[{"id":8171,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8164\/revisions\/8171"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8164"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8164"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8164"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}