Cuisine leetcode

Bienvenue à tous les braves dans la ville de leishu,Il y a des casseroles de cuisine dans la ville pour les braves,Pour se remettre en forme.

Il y a des numéros dans le sac à dos des braves 0 ~ 4 Cinq ingrédients,Parmi eux materials[j] Indique le paragraphe j Quantité de matériel végétal.Plusieurs plats peuvent être préparés à partir de ces ingrédients,cookbooks[i][j] Représente la production d'un i Pour la culture, il faut j Quantité de matériel végétal,Et attribute[i] = [x,y] Indique le paragraphe i La délicatesse de la cuisine x Et la satiété y.

Pas moins de limit Dans le cas de,S'il vous plaît revenir à la plus grande délicatesse disponible pour les braves.Si les besoins de satiété ne peuvent être satisfaits,Renvoie -1.

Attention!：

• Chaque préparation ne peut être faite qu'une seule fois.

Exemple 1：

Entrée：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

Produits：7

Explication：
La quantité d'ingrédients peut répondre aux deux options suivantes：
Programme I：Faire la cuisine 0 Et la cuisine 1,Pour obtenir une sensation de satiété 2+4、Delicious Degree 3+2
Programme II：Faire uniquement la cuisine 2, Peut se sentir plein pour 6、Le goût est 7
Donc, à la satisfaction de la satiété,Obtenez la plus grande délicatesse possible 7

Exemple 2：

Entrée：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

Produits：11

Explication： Par la fabrication de la nourriture 0 Et 1, Satiété suffisante , Et obtenir la plus grande délicatesse 11

Conseils：

• 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

C++

class Solution {
public:
    void dfs(vector<int>& materials, vector<vector<int>>& cookbooks, vector<vector<int>>& attribute, int k) {
        if(k==cookbooks.size()) {
            return;
        }
        for(int i=k;i<cookbooks.size();i++) {
            satiety+=attribute[i][1];
            yummy+=attribute[i][0];
            int flag=0;
            for(int j=0;j<5;j++) {
                used[j]+=cookbooks[i][j];
                if(used[j]>materials[j]) {
                    flag=1;
                }
            }
            if (flag == 0) {
                if (satiety >= limit) {
                    isFull=1;
                    res = max(res, yummy);
                }
                dfs(materials, cookbooks, attribute, i + 1);
            }
            for (int j = 0; j < 5; j++) {
                used[j] -= cookbooks[i][j];
            }
            satiety-=attribute[i][1];
            yummy-=attribute[i][0];
        }
    }

    int perfectMenu(vector<int>& materials, vector<vector<int>>& cookbooks, vector<vector<int>>& attribute, int limit) {
        used.resize(5);
        this->limit=limit;
        dfs(materials,cookbooks,attribute,0);
        if(isFull==0) {
            return -1;
        }
        return res;
    }
private:
    int satiety=0;
    int yummy=0;
    int isFull=0;
    std::vector<int> used;
    int limit;
    int res=0;
};