文章目錄

• • 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. 烹饪料理（状态枚举）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。