LeetCode 2022春季赛 2. 烹饪料理（状态枚举）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

欢迎各位勇者来到力扣城，城内设有烹饪锅供勇者制作料理，为自己恢复状态。

勇者背包内共有编号为 0 ~ 4 的五种食材，其中 meterials[j] 表示第 j 种食材的数量。
通过这些食材可以制作若干料理，cookbooks[i][j] 表示制作第 i 种料理需要第 j 种食材的数量，而 attribute[i] = [x,y] 表示第 i 道料理的美味度 x 和饱腹感 y。

在饱腹感不小于 limit 的情况下，请返回勇者可获得的最大美味度。
如果无法满足饱腹感要求，则返回 -1。

注意：
每种料理只能制作一次。

示例 1： 输入：meterials = [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： 输入：meterials = [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提示： meterials.length == 5 1 <= cookbooks.length == attribute.length <= 8 cookbooks[i].length == 5 attribute[i].length == 2 0 <= meterials[i], cookbooks[i][j], attribute[i][j] <= 20 1 <= limit <= 100

2. 解题

• 每种食物只能做一次，二进制01状态枚举，题目说 n 最大是 8，2^8 = 256，暴力枚举即可

class Solution { public:int perfectMenu(vector<int>& materials, vector<vector<int>>& cookbooks, vector<vector<int>>& attribute, int limit) {int n = cookbooks.size();int ans = -1;for(int i = 1; i < (1<<n); ++i){int full = 0, deli = 0;vector<int> cost(5, 0);bool ok = true;for(int j = 0; j < n; ++j){if((i>>j)&1) // i 状态哪些位是 1{for(int k = 0; k < 5; ++k){ // 花费的食材累加cost[k] += cookbooks[j][k];if(cost[k] > materials[k]){ // 超过食材限度ok = false;break;}}full += attribute[j][1]; // 饱腹感deli += attribute[j][0]; // 美味度}if(!ok)break;}if(ok && full >= limit){ans = max(ans, deli);}}return ans;} };

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

总结

以上是生活随笔为你收集整理的LeetCode 2022春季赛 2. 烹饪料理（状态枚举）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。