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

一【题目类别】

• 回溯

二【题目难度】

• 简单

三【题目编号】

• LCP 51.烹饪料理

四【题目描述】

• 欢迎各位勇者来到力扣城，城内设有烹饪锅供勇者制作料理，为自己恢复状态。
• 勇者背包内共有编号为 0 ~ 4 的五种食材，其中 materials[j] 表示第 j 种食材的数量。通过这些食材可以制作若干料理，cookbooks[i][j] 表示制作第 i 种料理需要第 j 种食材的数量，而 attribute[i] = [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[i].length == 5
• attribute[i].length == 2
• 0 <= materials[i], cookbooks[i][j], attribute[i][j] <= 20
• 1 <= limit <= 100

七【解题思路】

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

八【时间频度】

• 时间复杂度：$O(nm{2}^n)$，$n$为菜品个数，$m$为材料的数量
• 空间复杂度：$O(n)$，$n$为菜品个数

九【代码实现】

1. Java语言版

class Solution {// 初始化最大美味度为 -1（表示无法满足饱腹感条件时返回 -1）int maxRes = -1;public int perfectMenu(int[] materials, int[][] cookbooks, int[][] attribute, int limit) {// 记录每道菜是否做过boolean[] exists = new boolean[cookbooks.length];// 进行深度优先搜索dfs(materials, cookbooks, attribute, limit, exists, 0, 0);// 返回最大美味度return maxRes;}public void dfs(int[] materials, int[][] cookbooks, int[][] attribute, int limit, boolean[] exists, int sumx, int sumy) {// 如果总饱腹感 >= 限制值，更新最大美味度if (sumy >= limit) {maxRes = Math.max(sumx, maxRes);}// 获取菜谱总数int len = cookbooks.length;// 遍历每一道菜for (int i = 0; i < len; i++) {// 如果当前菜已经做过了，跳过if (exists[i]) {continue;}// 检查当前所剩的材料是否足够制作第 i 道料理int[] need = cookbooks[i];boolean canMake = true;for (int j = 0; j < need.length; j++) {if (materials[j] < need[j]) {canMake = false;break;}}// 可以制作这道菜if (canMake) {// 标记当前菜已经制作exists[i] = true;for (int j = 0; j < need.length; j++) {materials[j] -= need[j];}// 递归调用，继续制作其它菜，并更新美味度和饱腹感dfs(materials, cookbooks, attribute, limit, exists, sumx + attribute[i][0], sumy + attribute[i][1]);// 回溯：恢复材料，并标记这道菜为未制作for (int j = 0; j < need.length; j++) {materials[j] += need[j];}exists[i] = false;}}}}

2. Python语言版

class Solution:def __init__(self):# 初始化最大美味度为 -1（表示无法满足饱腹感条件时返回 -1）self.maxRes = -1def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:# 记录每道菜是否做过exists = [False] * len(cookbooks)# 进行深度优先搜索self.dfs(materials, cookbooks, attribute, limit, exists, 0, 0)# 返回最大美味度return self.maxResdef dfs(self, materials, cookbooks, attribute, limit, exists, sumx, sumy):"""深度优先搜索函数:param materials: List[int] 当前剩余的材料数量:param cookbooks: List[List[int]] 每道菜需要的材料数量:param attribute: List[List[int]] 每道菜的美味度和饱腹感:param limit: int 最小饱腹感限制:param exists: List[bool] 当前的菜是否已经制作:param sumx: int 当前总美味度:param sumy: int 当前总饱腹感"""# 如果总饱腹感 >= 限制值，更新最大美味度if sumy >= limit:self.maxRes = max(self.maxRes, sumx)# 获取菜谱总数len_cookbooks = len(cookbooks)# 遍历每一道菜for i in range(len_cookbooks):# 如果当前菜已经做过了，跳过if exists[i]:continue# 检查当前所剩的材料是否足够制作第 i 道料理need = cookbooks[i]can_make = Truefor j in range(len(need)):if materials[j] < need[j]:can_make = Falsebreak# 可以制作这道菜if can_make:# 标记当前菜已经制作exists[i] = True# 减去所需的材料for j in range(len(need)):materials[j] -= need[j]# 递归调用，继续制作其它菜，并更新美味度和饱腹感self.dfs(materials, cookbooks, attribute, limit, exists, sumx + attribute[i][0], sumy + attribute[i][1])# 回溯：恢复材料，并标记这道菜为未制作for j in range(len(need)):materials[j] += need[j]exists[i] = False

3. C语言版

// 初始化最大美味度为 -1（表示无法满足饱腹感条件时返回 -1）
int maxRes = -1;void dfs(int * materials, int materialsSize, int** cookbooks, int cookbooksSize, int** attribute, int limit, bool* exists, int sumx, int sumy)
{// 如果总饱腹感 >= 限制值，更新最大美味度if (sumy >= limit){if (sumx > maxRes) {maxRes = sumx;}}// 遍历每一道菜for (int i = 0; i < cookbooksSize; i++){// 如果当前菜已经做过了，跳过if (exists[i]){continue;}// 检查当前所剩的材料是否足够制作第 i 道料理bool canMake = true;for (int j = 0;j < materialsSize; j++){if (materials[j] < cookbooks[i][j]){canMake = false;break;}}// 可以制作这道菜if (canMake){// 标记当前菜已经制作exists[i] = true;for (int j = 0; j < materialsSize; j++){materials[j] -= cookbooks[i][j];}// 递归调用，继续制作其它菜，并更新美味度和饱腹感dfs(materials, materialsSize, cookbooks, cookbooksSize, attribute, limit, exists, sumx + attribute[i][0], sumy + attribute[i][1]);// 回溯：恢复材料，并标记这道菜为未制作for (int j = 0; j < materialsSize; j++){materials[j] += cookbooks[i][j];}exists[i] = false;}}
}int perfectMenu(int* materials, int materialsSize, int** cookbooks, int cookbooksSize, int* cookbooksColSize, int** attribute, int attributeSize, int* attributeColSize, int limit)
{// 初始化最大美味度为 -1（表示无法满足饱腹感条件时返回 -1）maxRes = -1;// 记录每道菜是否做过bool* exists = (bool*)malloc(cookbooksSize * sizeof(bool));for (int i = 0; i < cookbooksSize; i++) {exists[i] = false;}// 进行深度优先搜索dfs(materials, materialsSize, cookbooks, cookbooksSize, attribute, limit, exists, 0, 0);// 释放资源free(exists);// 返回最大美味度return maxRes;
}

十【提交结果】

1. Java语言版
   

2. Python语言版
   

3. C语言版