1000434. 烹饪料理

难度: Easy

题目描述

English description is not available for the problem. Please switch to Chinese.

解题思路

代码实现

解决方案

java

class Solution {

    public int perfectMenu(int[] materials, int[][] cookbooks, int[][] attribute, int limit) {
        return backTrace(cookbooks, new boolean[cookbooks.length], materials, attribute, limit, 0, 0);
    }

    private int backTrace(int[][] cookbooks, boolean[] isCooked, int[] materials, int[][] attribute, int limit, int x,
            int y) {
        int max = -1;
        if (y >= limit) {
            max = x;
        }
        int cM = cookbooks.length;
        int cN = cookbooks[0].length;

        for (int i = 0; i < cM; i++) {
            if (isCooked[i]) {
                continue;
            }

            int jLen = materials.length;
            boolean canCook = true;
            for (int j = 0; j < jLen; j++) {
                int cJ = cookbooks[i][j];
                if (cJ > materials[j]) {
                    canCook = false;
                    break;
                }

            }
            if (!canCook) {
                continue;
            }
            // 消耗食材
            isCooked[i] = true;
            for (int j = 0; j < jLen; j++) {
                materials[j] -= cookbooks[i][j];
            }

            int ax = attribute[i][0];
            int ay = attribute[i][1];
            max = Math.max(max, backTrace(cookbooks, isCooked, materials, attribute, limit, x + ax, y + ay));
            // 撤回
            isCooked[i] = false;
            for (int j = 0; j < jLen; j++) {
                materials[j] += cookbooks[i][j];
            }

        }

        return max;

    }

}