C++ 算法题：Perket 食谱 - 寻找最佳成分组合

"\u0009\u0009\u0009\u0009\u0009\u0009Perket" 是一道众所周知的美味佳肴。为了使 \u0009\u0009\u0009\u0009\u0009\u0009Perket 保持原样，厨师必须谨慎选择食材，以在保持传统风味的同时尽可能获得最大的味道。\n\n您有 \u0009N 种成分可供使用。 对于每种食物，我们都知道它的酸度 \u0009S 和苦味 \u0009B。当使用多种成分时，总酸度是所有成分的酸度量的乘积，总苦味是所有成分苦味量的总和。\n\n众所周知，\u0009\u0009\u0009\u0009\u0009\u0009Perket 既不酸也不苦。 我们要选择成分，以使酸味和苦味之间的绝对差最小。\n\n另外，必须使用至少一种成分。 你不能把水当做主菜。\n\n输入格式\n第一行包含整数 \u0009（\n1\n≤\n\u0009≤\n10\n）\nN（1≤N≤10），这是我们可以使用的成分数。\n\n接下来的 \u0009N 行中的每行包含两个整数，每个整数之间用空格隔开，即每种成分的酸味和苦味。\n\n输入数据将是这样的，如果我们用所有成分做饭，酸味和苦味都将小于 \n1000000000\n1000000000。\n\n输出格式\n输出酸味和苦味之间的最小差异。\n\n输入输出样例\n样例 1\n输入样例 复制\n1\n3 10\n\n输出样例 复制\n7\n样例 2\n输入样例 复制\n2\n3 8\n5 8\n\n输出样例 复制\n1\n样例 3\n输入样例 复制\n4\n1 7\n2 6\n3 8\n4 9\n输出样例 复制\n1\n样例说明\n在第三个示例中，我们选择最后三种成分。 那么总酸味为2·3·4 = 24，苦味为6 + 8 + 9 = 23。 区别是1。\n这道题目可以使用回溯法解决。对于每一种成分，我们可以选择使用或者不使用，然后递归处理下一种成分。\n\n具体实现如下：\n\ncpp\n#include <iostream>\n#include <vector>\n#include <algorithm>\n\nusing namespace std;\n\nint N; \nvector<pair<int, int>> ingredients; \nint minDifference = INT_MAX; \n\nvoid backtrack(int index, int acidity, int bitterness) {\n if (index == N) {\n minDifference = min(minDifference, abs(acidity - bitterness));\n return; \n }\n\n // 不使用当前成分\n backtrack(index + 1, acidity, bitterness);\n\n // 使用当前成分\n int acid = ingredients[index].first;\n int bitter = ingredients[index].second; \n backtrack(index + 1, acidity * acid, bitterness + bitter); \n}\n\nint main() {\n cin >> N; \n for (int i = 0; i < N; i++) {\n int acid, bitter; \n cin >> acid >> bitter; \n ingredients.push_back(make_pair(acid, bitter)); \n }\n\n backtrack(0, 1, 0); \n\n cout << minDifference << endl; \n\n return 0; \n}\n\n\n时间复杂度分析：回溯法的时间复杂度是指数级别的，因为对于每一种成分，我们都有两种选择：使用或者不使用。所以总的时间复杂度为O(2^N)，其中N为成分的个数。