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. }
    11. int sx = 0, sy = 0;
    12. for (int i = 0; i < n; i++) {
    13. if (S & (1 << i)) {
    14. for (int j = 0; j < 5; j++) {
    15. ps[j] += cookbooks[i][j];
    16. }
    17. sx += attribute[i][0];
    18. sy += attribute[i][1];
    19. }
    20. }
    21. bool valid = true;
    22. for (int j = 0; j < 5; j++) {
    23. // cout << ps[j] << " ";
    24. if (ps[j] > materials[j]) {
    25. valid = false;
    26. }
    27. }
    28. if (valid && sy >= limit) {
    29. ans = max(ans, sx);
    30. }
    31. }
    32. return ans;
    33. }
    34. };

    思路2:回溯todo