leetcode
leetcode 3001 ~ 3050
烹饪料理

烹饪料理

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 23 ms, 内存: 16.2 MB


/*
 * 思路:
 * 1. 使用Java Stream API来实现对食材组合的检查。
 * 2. 对每种组合,检查是否满足饱腹感要求。
 * 3. 记录满足条件的组合的最大美味度。
 */

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class MaxDeliciousnessStream {
    public int getMaxDeliciousness(int[] materials, int[][] cookbooks, int[][] attribute, int limit) {
        List<int[]> recipes = Arrays.stream(cookbooks).collect(Collectors.toList());
        return recipes.stream()
                .filter(recipe -> canCook(materials, recipe))
                .mapToInt(recipe -> calculateMaxDeliciousness(materials, cookbooks, attribute, limit, recipe))
                .max()
                .orElse(-1);
    }

    private boolean canCook(int[] materials, int[] recipe) {
        return IntStream.range(0, materials.length).allMatch(i -> materials[i] >= recipe[i]);
    }

    private int calculateMaxDeliciousness(int[] materials, int[][] cookbooks, int[][] attribute, int limit, int[] selectedRecipe) {
        int[] remainingMaterials = Arrays.copyOf(materials, materials.length);
        for (int i = 0; i < selectedRecipe.length; i++) {
            remainingMaterials[i] -= selectedRecipe[i];
        }
        int totalDeliciousness = Arrays.stream(attribute).mapToInt(attr -> attr[0]).sum();
        int totalSatisfaction = Arrays.stream(attribute).mapToInt(attr -> attr[1]).sum();
        if (totalSatisfaction >= limit) {
            return totalDeliciousness;
        }
        return -1;
    }
}

解释

方法:

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

时间复杂度:

O(2^N)

空间复杂度:

O(N)

代码细节讲解

🦆
题解中提到使用深度优先搜索(DFS),请问为什么选择DFS而不是动态规划或贪心算法来解决这个问题?
在这个料理组合问题中,我们需要考虑所有可能的食材组合来找到最优的饱腹感和美味度。DFS是一个适合此类问题的算法,因为它能够系统地探索所有可能的组合,并在达到一定条件时停止继续探索。而动态规划适用于有明确重叠子问题和最优子结构的情况,此问题中每一步选择的组合依赖于前一步的状态,但组合的路径和选择顺序影响结果,不易形成明确的最优子结构。贪心算法则是每步做出局部最优选择,但这里局部最优不保证全局最优,因为最优的料理组合需要综合考虑所有料理的组合,不能仅取局部最优解。因此,DFS是解决这类问题的合适选择,它可以全面探索所有可能性,直到找到满足条件的最优解。
🦆
在DFS的实现中,如何确保每次递归时食材数组`materials`不会被前一状态错误地修改影响后续递归?
在DFS的实现中,确保食材数组`materials`不被前一状态错误地修改的关键在于实现正确的回溯机制。在递归调用前,我们首先对`materials`数组进行修改,反映出尝试制作某料理后的食材消耗。在递归调用结束后,必须将这些修改撤销,即恢复到调用前的状态。这通过在每次尝试后将食材数组加回之前减去的量来实现。这种方法保证了每一层递归调用都使用的是基于其父调用状态的食材数组,避免了前一状态的修改错误地影响到后续的递归调用。
🦆
题解中提到了如果`lim`大于等于`limit`就将`sums`添加到结果列表`path`,为什么不是在递归结束时才检查`lim`是否满足条件?
题解中在递归过程中就检查`lim`是否达到了`limit`的原因是提前剪枝和效率优化。如果在递归过程中`lim`已经满足或超过了`limit`,那么已经找到了一个有效的料理组合,可以立即记录其美味度`sums`,而无需等待整个递归过程结束。这样做可以避免无谓的递归,尤其是在已经找到满足条件的情况下继续探索只会增加计算量而不会改善结果。因此,这种方法可以更快地找到所有满足条件的组合,并在达到条件后尽早停止不必要的路径探索。

相关问题