class Solution {
public:
int perfectMenu(vector<int>& materials, vector<vector<int>>& cookbooks, vector<vector<int>>& attribute, int limit) {
}
};
LCP 51. 烹饪料理
欢迎各位勇者来到力扣城，城内设有烹饪锅供勇者制作料理，为自己恢复状态。
勇者背包内共有编号为 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 == 51 <= cookbooks.length == attribute.length <= 8cookbooks[i].length == 5attribute[i].length == 20 <= materials[i], cookbooks[i][j], attribute[i][j] <= 201 <= limit <= 100原站题解
rust 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-09-13 16:13:28
impl Solution {
// 解法一
pub fn perfect_menu(materials: Vec<i32>, cookbooks: Vec<Vec<i32>>, attribute: Vec<Vec<i32>>, limit: i32) -> i32 {
fn recall(m:Vec<i32>, c:&[Vec<i32>], a:&[Vec<i32>], limit:i32) -> Option<i32> {
let mut yami_max=0;
'c:for (h,cook) in c.iter().enumerate(){
let mut tmp=m.clone();
for i in 0..5{
if tmp[i]<cook[i]{
continue 'c;
}else{
tmp[i]-=cook[i];
}
}
let mut yami=a[h][0];
match recall(tmp,&c[h+1..],&a[h+1..],limit-a[h][1]){
Some(a)=>yami+=a,
None=>continue,
}
yami_max=yami_max.max(yami);
}
if yami_max==0&&limit>0{
None
}else{
Some(yami_max)
}
}
match recall(materials,&cookbooks[..],&attribute[..],limit){
Some(a)=>a,
None=>-1,
}
}
// 解法二
pub fn perfect_menu2(materials: Vec<i32>, cookbooks: Vec<Vec<i32>>, attribute: Vec<Vec<i32>>, limit: i32) -> i32 {
let n = cookbooks.len();
let m = materials.len();
let mut ans = -1;
for i in 0..(1<<n) {
let mut tmp = vec![0;m];
let mut x = 0;
let mut y = 0;
for j in 0..n {
if (i >> j & 1) != 0 {
for k in 0..m {
tmp[k] += cookbooks[j][k];
}
x += attribute[j][0];
y += attribute[j][1];
}
}
let mut ok = true;
for j in 0..m {
if tmp[j] > materials[j] {
ok = false;
break;
}
}
if ok && y >= limit {
ans = ans.max(x);
}
}
ans
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 2.4 MB, 提交时间: 2023-09-13 16:11:15
// 回溯
func perfectMenu(materials []int, cookbooks [][]int, attribute [][]int, limit int) int {
ans:=-1
n:=len(cookbooks)
//从第cur道菜开始尝试，当前美味度sa，当前饱满度sb，当前剩余食材数组mat，寻找可能达到的美味度数的最大值
var dfs func(cur,sa,sb int, mat []int)
dfs =func(cur,sa,sb int, mat []int){
if sb>=limit{
ans=max(sa,ans)
}
for i:=cur;i<n;i++{
if check(mat,cookbooks[i]){
cura:=attribute[i]
nxt:=make([]int,5)
for j:=0;j<5;j++{
nxt[j]=mat[j]-cookbooks[i][j]
}
dfs(i+1,sa+cura[0],sb+cura[1],nxt)
}
}
}
dfs(0,0,0,materials)
return ans
}
func check(a, b []int) bool { for i:=0; i<5; i++ { if a[i] < b[i] { return false }; }; return true }
func max(a, b int) int { if a > b { return a }; return b }
python3 解法, 执行用时: 112 ms, 内存消耗: 15 MB, 提交时间: 2022-06-14 17:53:31
class Solution:
def perfectMenu(self, materials: List[int], cookbooks: List[List[int]], attribute: List[List[int]], limit: int) -> int:
n = len(cookbooks)
m = len(cookbooks[0])
ans = -1
for i in range(1, 1 << n):
x, y, s = 0, 0, [0] * m
for j in range(n):
if (i & (1 << j)) != 0:
s = [si + mi for si, mi in zip(s, cookbooks[j])]
x += attribute[j][0]
y += attribute[j][1]
if y >= limit and all(si <= mi for si, mi in zip(s, materials)):
ans = max(ans, x)
return ans