LCP51.烹饪料理

image.png

思路1：二进制枚举

  • 从低位向高位枚举，最低位的1表示选用cookbook中编号为0的食谱，倒数第2低的1表示选用cookbook中编号为1的食谱，以此类推。
  • for (int S = 0; S < (1<<n); ++S)表示枚举LCP51.烹饪料理 - 图2种可能，遍历了所有情况。

  • if (S & (1 << i))表示第i低位是1，选用了对应位置的食谱。

    代码1：

    1. class Solution {
    2. public:
    3.   int perfectMenu(vector<int>& materials, vector<vector<int>>& cookbooks, vector<vector<int>>& attribute, int limit) {
    4.       int n = cookbooks.size();
    5.       int ps[10];
    6.       int ans = -1;
    7.       for (int S = 0; S < (1 << n); S++) {
    8.           for (int i = 0; i < 5; i++) {
    9.               ps[i] = 0;
    10.           }
    12.           int sx = 0, sy = 0;
    13.           for (int i = 0; i < n; i++) {
    14.               if (S & (1 << i)) {
    15.                   for (int j = 0; j < 5; j++) {
    16.                       ps[j] += cookbooks[i][j];
    17.                   }
    18.                   sx += attribute[i][0];
    19.                   sy += attribute[i][1];
    20.               }
    21.           }
    23.           bool valid = true;
    24.           for (int j = 0; j < 5; j++) {
    25.               // cout << ps[j] << " ";
    26.               if (ps[j] > materials[j]) {
    27.                   valid = false;
    28.               }
    29.           }
    31.           if (valid && sy >= limit) {
    32.               ans = max(ans, sx);
    33.           }
    34.       }
    36.       return ans;
    37.   }
    38. };

    思路2：回溯todo