Day135 | 灵神 | 回溯算法 | 子集型 烹饪料理

LCP 51.烹饪料理

LCP 51. 烹饪料理 - 力扣（LeetCode）

思路：

思路比较好想

笔者用的是选或不选的思路，即看第 i种选或不选，如果食材足够就选（choicei进行判断），如果食材不足就不选，直接去看i+1选或不选

选的话就把食材饱腹感美味度给修改了，不选的话就直接递归就行

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    int res=-1;
    //还够不够选第i种
    bool choicei(vector<int>& materials, vector<vector<int>>& cookbooks,int i)
    {
        for(int j=0;j<materials.size();j++)
            if(materials[j]<cookbooks[i][j])    
                return false;
        return true;
    }
    //f是美味度，i遍历的是cookbooks
    void dfs(vector<int>& materials, vector<vector<int>>& cookbooks, vector<vector<int>>& attribute, int limit,int f,int i)
    {
        if(i==cookbooks.size())
        {
            if(limit<=0)
                res=max(res,f);
            return ;
        }
        //选第i种
        if(choicei(materials,cookbooks,i))
        {
            for(int j=0;j<materials.size();j++)
                materials[j]-=cookbooks[i][j];
            //美味度加上第i种的
            f+=attribute[i][0];
            //饱腹感减去第i种的
            limit-=attribute[i][1];
            dfs(materials,cookbooks,attribute,limit,f,i+1);
            //恢复现场
            for(int j=0;j<materials.size();j++)
                materials[j]+=cookbooks[i][j];
            f-=attribute[i][0];
            limit+=attribute[i][1];
        }
        //不选第i种
        dfs(materials,cookbooks,attribute,limit,f,i+1);
    }
    int perfectMenu(vector<int>& materials, vector<vector<int>>& cookbooks, vector<vector<int>>& attribute, int limit) {
        dfs(materials,cookbooks,attribute,limit,0,0);
        return res;
    }
};