题目

leetcode原题链接

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

思路

在这里插入图片描述

每道料理可选可不选（材料足够时可选），可以使用回溯
返回条件是每一道料理都遍历过了（即选了或没选），索引超出料理数组最大索引，此时判断饱腹感y是否满足要求，满足则更新结果。最后记得返回。
循环遍历当前料理后的每一道料理，如果材料还够就选择该料里
回溯时要判断该料理是否选择了，选择了要归还材料并还原x、y

做题时忽略了题目要求：如果无法满足饱腹感要求，则返回 -1。所以记得res初始化为-1

代码

在这里插入图片描述

var perfectMenu = function (materials, cookbooks, attribute, limit) {let len = cookbooks.lengthlet res = -1backtracking(0, 0, 0)return resfunction backtracking(startIndex, x, y) {if (startIndex >= len) {// 饱腹感满足要求才更新美味度if (y >= limit) {res = Math.max(res, x)}return}// 遍历每一道料理for (let i = startIndex; i < len; i++) {// 得到该料理的每一种材料需求let [a, b, c, d, e] = [...cookbooks[i]]// flag用于标记该道料理有没有被选择，方便回溯的时候将材料归还回去let flag = 0// 所有材料都够用才选择该料理if (a <= materials[0] && b <= materials[1] && c <= materials[2] && d <= materials[3] && e <= materials[4]) {// 更新美味度和饱腹感x += attribute[i][0]y += attribute[i][1]// 消耗材料materials[0] -= amaterials[1] -= bmaterials[2] -= cmaterials[3] -= dmaterials[4] -= e// 标记选择了该料理flag = 1}// 递归下一道料理backtracking(i + 1, x, y)// 回溯回来，根据flag判断用不用归还材料和还原美味度、饱腹感if (flag) {x -= attribute[i][0]y -= attribute[i][1]materials[0] += amaterials[1] += bmaterials[2] += cmaterials[3] += dmaterials[4] += e}}
}}