【题目来源】
洛谷：P2036 [COCI 2008/2009 #2] PERKET - 洛谷 (luogu.com.cn)
【题目描述】
Perket 是一种流行的美食。为了做好 Perket，厨师必须谨慎选择食材，以在保持传统风味的同时尽可能获得最全面的味道。你有 \(n\) 种可支配的配料。对于每一种配料，我们知道它们各自的酸度 \(s\) 和苦度 \(b\)。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的苦度为每一种配料的苦度的总和。
众所周知，美食应该做到口感适中，所以我们希望选取配料，以使得酸度和苦度的绝对差最小。
另外，我们必须添加至少一种配料，因为没有任何食物以水为配料的。
【输入】
第一行一个整数 \(n\)，表示可供选用的食材种类数。
接下来 \(n\) 行，每行 \(2\) 个整数 \(s_i\) 和 \(b_i\)，表示第 \(i\) 种食材的酸度和苦度。
【输出】
一行一个整数，表示可能的总酸度和总苦度的最小绝对差。
【输入样例】
2
3 8
5 8
【输出样例】
1
【解题思路】
【算法标签】
《洛谷 P2036 PERKET》 #模拟# #搜索# #COCI# #2008#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 定义全局变量：
// n - 食材的数量
// s[25] - 存储每种食材的酸度值
// b[25] - 存储每种食材的苦度值
// ans - 存储最终的最小差值，初始设为一个大数(1e9)
int n, s[25], b[25], ans = 1e9;// 递归函数f：
// sd - 当前累积的酸度乘积（初始为1）
// kd - 当前累积的苦度总和（初始为0）
// step - 当前处理的食材序号（从0开始）
void f(int sd, int kd, int step)
{// 递归终止条件：处理完所有食材if (step == n) {// 计算当前选择的酸度积和苦度和的绝对差int tmp = abs(sd - kd);// 只有当至少选择了一种食材（kd!=0）且差值更小时，才更新ansif (tmp < ans && kd != 0) ans = tmp;return;}step++; // 移动到下一个食材// 递归分支1：选择当前食材// 酸度相乘，苦度相加f(sd * s[step], kd + b[step], step);// 递归分支2：不选择当前食材// 保持原样进入下一层f(sd, kd, step);
}int main()
{// 输入食材数量ncin >> n;// 输入每种食材的酸度s[i]和苦度b[i]for (int i = 1; i <= n; i++) cin >> s[i] >> b[i];// 开始递归，初始状态：酸度积1，苦度和0，从第0步开始f(1, 0, 0);// 输出最小的酸苦差值cout << ans;return 0;
}
【运行结果】
2
3 8
5 8
1