【LeetCode每日一题】——LCP 51.烹饪料理

一【题目种别】

• 回溯
  

二【题目难度】

• 简单
  

三【题目编号】

• LCP 51.烹饪料理
  

四【题目形貌】

• 接待各位勇者来到力扣城，城内设有烹饪锅供勇者制作料理，为自己恢复状态。
  
• 勇者背包内共有编号为 0 ~ 4 的五种食材，此中 materials[j] 表现第 j 种食材的数目。通过这些食材可以制作多少料理，cookbooks[j] 表现制作第 i 种料理需要第 j 种食材的数目，而 attribute = [x,y] 表现第 i 道料理的美味度 x 和饱腹感 y。
  
• 在饱腹感不小于 limit 的环境下，请返回勇者可得到的最大美味度。如果无法满足饱腹感要求，则返回 -1。
  
• 注意：
  
  
  
  • 每种料理只能制作一次。
    
  
  

五【题目示例】

• 示例 1：
  
  
  
  • 输入：materials = [3,2,4,1,2] cookbooks = [[1,1,0,1,2],[2,1,4,0,0],[3,2,4,1,0]] attribute = [[3,2],[2,4],[7,6]] limit = 5
    
  • 输出：7
    
  • 解释： 食材数目可以满足以下两种方案： 方案一：制作料理 0 和料理 1，可得到饱腹感 2+4、美味度 3+2 方案二：仅制作料理 2， 可饱腹感为 6、美味度为 7 因此在满足饱腹感的要求下，可得到最高美味度 7
    
  
  
• 示例 2：
  
  
  
  • 输入：materials = [10,10,10,10,10] cookbooks = [[1,1,1,1,1],[3,3,3,3,3],[10,10,10,10,10]] attribute = [[5,5],[6,6],[10,10]] limit = 1
    
  • 输出：11
    
  • 解释：通过制作料理 0 和 1，可满足饱腹感，并得到最高美味度 11
    
  
  

六【题目提示】

• materials.length == 5
  
• 1 <= cookbooks.length == attribute.length <= 8
  
• cookbooks.length == 5
  
• attribute.length == 2
  
• 0 <= materials, cookbooks[j], attribute[j] <= 20
  
• 1 <= limit <= 100
  

七【解题思绪】

• 该题是回溯算法的经典应用，其实我以为挺好理解，符合人的根本直觉，主要是要把题目读懂
  
• 既然是回溯，我们就要确定何时结束递归，根据题目形貌：“如果总饱腹感 >= 限定值，更新最大美味度”，以是这就是递归退出的条件，最后我们需要返回“最大美味度”
  
• 那么核心递归过程呢？其实也很简单
  
  
  
  • 我们遍历每一道菜，对于每道菜我们起首需要检查这道菜是否已经做过了，如果做过了就跳过，否则继续下面的操纵（题目要求每道菜只能做一次）
    
  • 然后再检查当前剩的食材的数目还能否支持做完这道菜，如果不能那就结束，回到上一个状态，否则继续下面的操纵
    
  • 如果当前这道菜通过了所有检查，那么需要开始举行回溯操纵
    
    
    
    • 标志这道菜已经做了
      
    • 继续做别的菜，并更新美味度和饱腹感
      
    • 回溯，恢复材料，并标志这道菜还未做
      
    
    
  
  
• 可以发现，以上整个过程就是回溯算法的标准模板，只不过根据题目要求添加了一些检查而已
  
• 最后返回回溯盘算得到的“最大美味度”即可，具体细节可以参考下面的代码
  

八【时间频度】

• 时间复杂度：                                        O                            (                            n                            m                                       2                               n                                      )                                  O(nm2^n)                     O(nm2n)，                                        n                                  n                     n为菜品个数，                                        m                                  m                     m为材料的数目
  
• 空间复杂度：                                        O                            (                            n                            )                                  O(n)                     O(n)，                                        n                                  n                     n为菜品个数
  

九【代码实现】

• Java语言版
  

1. class Solution {
3.     // 初始化最大美味度为 -1（表示无法满足饱腹感条件时返回 -1）
4.     int maxRes = -1;
6.     public int perfectMenu(int[] materials, int[][] cookbooks, int[][] attribute, int limit) {
7.         // 记录每道菜是否做过
8.         boolean[] exists = new boolean[cookbooks.length];
9.         // 进行深度优先搜索
10.         dfs(materials, cookbooks, attribute, limit, exists, 0, 0);
11.         // 返回最大美味度
12.         return maxRes;
13.     }
15.     public void dfs(int[] materials, int[][] cookbooks, int[][] attribute, int limit, boolean[] exists, int sumx, int sumy) {
16.         // 如果总饱腹感 >= 限制值，更新最大美味度
17.         if (sumy >= limit) {
18.             maxRes = Math.max(sumx, maxRes);
19.         }
20.         // 获取菜谱总数
21.         int len = cookbooks.length;
22.         // 遍历每一道菜
23.         for (int i = 0; i < len; i++) {
24.             // 如果当前菜已经做过了，跳过
25.             if (exists[i]) {
26.                 continue;
27.             }
28.             // 检查当前所剩的材料是否足够制作第 i 道料理
29.             int[] need = cookbooks[i];
30.             boolean canMake = true;
31.             for (int j = 0; j < need.length; j++) {
32.                 if (materials[j] < need[j]) {
33.                     canMake = false;
34.                     break;
35.                 }
36.             }
37.             // 可以制作这道菜
38.             if (canMake) {
39.                 // 标记当前菜已经制作
40.                 exists[i] = true;
41.                 for (int j = 0; j < need.length; j++) {
42.                     materials[j] -= need[j];
43.                 }
44.                 // 递归调用，继续制作其它菜，并更新美味度和饱腹感
45.                 dfs(materials, cookbooks, attribute, limit, exists, sumx + attribute[i][0], sumy + attribute[i][1]);
46.                 // 回溯：恢复材料，并标记这道菜为未制作
47.                 for (int j = 0; j < need.length; j++) {
48.                     materials[j] += need[j];
49.                 }
50.                 exists[i] = false;
51.             }
52.         }
53.     }
55. }

复制代码

• Python语言版
  

1. class Solution:
3.     def __init__(self):
4.         # 初始化最大美味度为 -1（表示无法满足饱腹感条件时返回 -1）
5.         self.maxRes = -1
7.     def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:
8.         # 记录每道菜是否做过
9.         exists = [False] * len(cookbooks)
10.         # 进行深度优先搜索
11.         self.dfs(materials, cookbooks, attribute, limit, exists, 0, 0)
12.         # 返回最大美味度
13.         return self.maxRes
15.     def dfs(self, materials, cookbooks, attribute, limit, exists, sumx, sumy):
16.         """
17.         深度优先搜索函数
18.         :param materials: List[int] 当前剩余的材料数量
19.         :param cookbooks: List[List[int]] 每道菜需要的材料数量
20.         :param attribute: List[List[int]] 每道菜的美味度和饱腹感
21.         :param limit: int 最小饱腹感限制
22.         :param exists: List[bool] 当前的菜是否已经制作
23.         :param sumx: int 当前总美味度
24.         :param sumy: int 当前总饱腹感
25.         """
26.         # 如果总饱腹感 >= 限制值，更新最大美味度
27.         if sumy >= limit:
28.             self.maxRes = max(self.maxRes, sumx)
29.         # 获取菜谱总数
30.         len_cookbooks = len(cookbooks)
31.         # 遍历每一道菜
32.         for i in range(len_cookbooks):
33.             # 如果当前菜已经做过了，跳过
34.             if exists[i]:
35.                 continue
36.             # 检查当前所剩的材料是否足够制作第 i 道料理
37.             need = cookbooks[i]
38.             can_make = True
39.             for j in range(len(need)):
40.                 if materials[j] < need[j]:
41.                     can_make = False
42.                     break
43.             # 可以制作这道菜
44.             if can_make:
45.                 # 标记当前菜已经制作
46.                 exists[i] = True
47.                 # 减去所需的材料
48.                 for j in range(len(need)):
49.                     materials[j] -= need[j]
50.                 # 递归调用，继续制作其它菜，并更新美味度和饱腹感
51.                 self.dfs(materials, cookbooks, attribute, limit, exists, sumx + attribute[i][0], sumy + attribute[i][1])
52.                 # 回溯：恢复材料，并标记这道菜为未制作
53.                 for j in range(len(need)):
54.                     materials[j] += need[j]
55.                 exists[i] = False

复制代码

• C语言版
  

1. // 初始化最大美味度为 -1（表示无法满足饱腹感条件时返回 -1）
2. int maxRes = -1;
4. void dfs(int * materials, int materialsSize, int** cookbooks, int cookbooksSize, int** attribute, int limit, bool* exists, int sumx, int sumy)
5. {
6.     // 如果总饱腹感 >= 限制值，更新最大美味度
7.     if (sumy >= limit)
8.     {
9.         if (sumx > maxRes) {
10.             maxRes = sumx;
11.         }
12.     }
13.     // 遍历每一道菜
14.     for (int i = 0; i < cookbooksSize; i++)
15.     {
16.         // 如果当前菜已经做过了，跳过
17.         if (exists[i])
18.         {
19.             continue;
20.         }
21.         // 检查当前所剩的材料是否足够制作第 i 道料理
22.         bool canMake = true;
23.         for (int j = 0;j < materialsSize; j++)
24.         {
25.             if (materials[j] < cookbooks[i][j])
26.             {
27.                 canMake = false;
28.                 break;
29.             }
30.         }
31.         // 可以制作这道菜
32.         if (canMake)
33.         {
34.             // 标记当前菜已经制作
35.             exists[i] = true;
36.             for (int j = 0; j < materialsSize; j++)
37.             {
38.                 materials[j] -= cookbooks[i][j];
39.             }
40.             // 递归调用，继续制作其它菜，并更新美味度和饱腹感
41.             dfs(materials, materialsSize, cookbooks, cookbooksSize, attribute, limit, exists, sumx + attribute[i][0], sumy + attribute[i][1]);
42.             // 回溯：恢复材料，并标记这道菜为未制作
43.             for (int j = 0; j < materialsSize; j++)
44.             {
45.                 materials[j] += cookbooks[i][j];
46.             }
47.             exists[i] = false;
48.         }
49.     }
50. }
52. int perfectMenu(int* materials, int materialsSize, int** cookbooks, int cookbooksSize, int* cookbooksColSize, int** attribute, int attributeSize, int* attributeColSize, int limit)
53. {
54.     // 初始化最大美味度为 -1（表示无法满足饱腹感条件时返回 -1）
55.     maxRes = -1;
56.     // 记录每道菜是否做过
57.     bool* exists = (bool*)malloc(cookbooksSize * sizeof(bool));
58.     for (int i = 0; i < cookbooksSize; i++) {
59.         exists[i] = false;
60.     }
61.     // 进行深度优先搜索
62.     dfs(materials, materialsSize, cookbooks, cookbooksSize, attribute, limit, exists, 0, 0);
63.     // 释放资源
64.     free(exists);
65.     // 返回最大美味度
66.     return maxRes;
67. }

复制代码

十【提交结果】

• Java语言版
  
  
  
  
• Python语言版
  
  
  
  
• C语言版
  
  
  
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。