烹饪料理

难度: Easy

欢迎各位勇者来到力扣城，城内设有烹饪锅供勇者制作料理，为自己恢复状态。勇者背包内共有编号为 `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`

Submission

运行时间: 23 ms

内存: 16.2 MB

class Solution:
    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:
        lim=0
        sums=0
        path=[]
        def dfs(i,materials,lim,sums):
            if min(materials)<0:
                return
            if lim>=limit:
                path.append(sums)
            for x in range(i,len(cookbooks)):
                materials = [materials[s]-cookbooks[x][s] for s in range(0,len(materials))]
                lim+=attribute[x][1]
                sums+=attribute[x][0]
                dfs(x+1,materials,lim,sums)
                materials=[materials[s]+cookbooks[x][s] for s in range(0,len(materials))]
                lim-=attribute[x][1]
                sums-=attribute[x][0]
        dfs(0,materials,lim,sums)
        if len(path)==0:
            return -1
        else:
            return max(path)

Explain

该题解采用了深度优先搜索（DFS）的方法来遍历所有可能的料理组合。通过递归探索制作每种料理的可能性，并对每种组合的饱腹感和美味度进行累加。当所有食材都足够时，检查当前的饱腹感是否满足限制条件，如果满足，则将当前的美味度加入到结果列表中。最终，从结果列表中取最大值作为答案。如果列表为空，表示没有任何料理组合能满足饱腹感要求，此时返回-1。

时间复杂度: O(2^N)

空间复杂度: O(N)

class Solution:
    def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:
        # 初始化饱腹感和美味度和
        lim=0
        sums=0
        # 结果列表，用于存储满足饱腹感的所有美味度总和
        path=[]
        # 定义深度优先搜索函数
        def dfs(i,materials,lim,sums):
            # 如果食材不足，则返回
            if min(materials)<0:
                return
            # 如果当前饱腹感已满足要求，记录美味度总和
            if lim>=limit:
                path.append(sums)
            # 遍历所有料理
            for x in range(i,len(cookbooks)):
                # 尝试制作料理x，更新食材数量、饱腹感和美味度
                materials = [materials[s]-cookbooks[x][s] for s in range(0,len(materials))]
                lim+=attribute[x][1]
                sums+=attribute[x][0]
                dfs(x+1,materials,lim,sums)
                # 回溯，恢复食材数量、饱腹感和美味度
                materials=[materials[s]+cookbooks[x][s] for s in range(0,len(materials))]
                lim-=attribute[x][1]
                sums-=attribute[x][0]
        # 开始DFS搜索
        dfs(0,materials,lim,sums)
        # 如果没有合法的料理组合，返回-1，否则返回最大美味度
        if len(path)==0:
            return -1
        else:
            return max(path)

Explore

在这个料理组合问题中，我们需要考虑所有可能的食材组合来找到最优的饱腹感和美味度。DFS是一个适合此类问题的算法，因为它能够系统地探索所有可能的组合，并在达到一定条件时停止继续探索。而动态规划适用于有明确重叠子问题和最优子结构的情况，此问题中每一步选择的组合依赖于前一步的状态，但组合的路径和选择顺序影响结果，不易形成明确的最优子结构。贪心算法则是每步做出局部最优选择，但这里局部最优不保证全局最优，因为最优的料理组合需要综合考虑所有料理的组合，不能仅取局部最优解。因此，DFS是解决这类问题的合适选择，它可以全面探索所有可能性，直到找到满足条件的最优解。

在DFS的实现中，确保食材数组`materials`不被前一状态错误地修改的关键在于实现正确的回溯机制。在递归调用前，我们首先对`materials`数组进行修改，反映出尝试制作某料理后的食材消耗。在递归调用结束后，必须将这些修改撤销，即恢复到调用前的状态。这通过在每次尝试后将食材数组加回之前减去的量来实现。这种方法保证了每一层递归调用都使用的是基于其父调用状态的食材数组，避免了前一状态的修改错误地影响到后续的递归调用。

题解中在递归过程中就检查`lim`是否达到了`limit`的原因是提前剪枝和效率优化。如果在递归过程中`lim`已经满足或超过了`limit`，那么已经找到了一个有效的料理组合，可以立即记录其美味度`sums`，而无需等待整个递归过程结束。这样做可以避免无谓的递归，尤其是在已经找到满足条件的情况下继续探索只会增加计算量而不会改善结果。因此，这种方法可以更快地找到所有满足条件的组合，并在达到条件后尽早停止不必要的路径探索。