【题解】【子集枚举】—— PERKET
[COCI2008-2009 #2] PERKET
题目描述
Perket 是一种流行的美食。为了做好 Perket，厨师必须谨慎选择食材，以在保持传统风味的同时尽可能获得最全面的味道。你有 n n n 种可支配的配料。对于每一种配料，我们知道它们各自的酸度 s s s 和苦度 b b b。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的苦度为每一种配料的苦度的总和。
众所周知，美食应该做到口感适中，所以我们希望选取配料，以使得酸度和苦度的绝对差最小。
另外，我们必须添加至少一种配料，因为没有任何食物以水为配料的。
输入格式
第一行一个整数 n n n，表示可供选用的食材种类数。
接下来 n n n 行，每行 2 2 2 个整数 s i s_i si 和 b i b_i bi，表示第 i i i 种食材的酸度和苦度。
输出格式
一行一个整数，表示可能的总酸度和总苦度的最小绝对差。
输入输出样例
输入 #1
1
3 10
输出 #1
7
输入 #2
2
3 8
5 8
输出 #2
1
输入 #3
4
1 7
2 6
3 8
4 9
输出 #3
1
提示
数据规模与约定
对于 100 % 100\% 100% 的数据，有 1 ≤ n ≤ 10 1 \leq n \leq 10 1≤n≤10，且将所有可用食材全部使用产生的总酸度和总苦度小于 1 × 1 0 9 1 \times 10^9 1×109，酸度和苦度不同时为 1 1 1 和 0 0 0。
说明
- 本题满分 70 70 70 分。
- 题目译自 COCI2008-2009 CONTEST #2 PERKET，译者 @mnesia。
1.思路解析
直接根据题意模拟，然后使用子集枚举更新答案就行了。
2.AC代码
#include<bits/stdc++.h>
using namespace std;
struct batching//记录每种配料的信息
{
int s,b;//酸度和苦度
}a[20];
int main()
{
int n,ans=INT_MAX;//用ans记录答案
cin>>n;
for(int i=1;i<=n;i++)//输入酸度和苦度
cin>>a[i].s>>a[i].b;
for(int i=1;i<=n;i++)//枚举放入1到n种配料
for(int S=0;S<1<<n;S++)//从空集枚举到全集
if(__builtin_popcount(S)==i)//枚举寻找i元子集
{
int sn=1,bs=0;//酸度积和苦度和
for(int j=1;j<=n;j++)//枚举判断子集中每个数是否出现
if(S&1<<(j-1))//如果出现了
sn*=a[j].s,bs+=a[j].b;//更新酸度积和苦度和
ans=min(abs(sn-bs),ans);//更新答案
}
cout<<ans;
return 0;
}
喜欢就订阅此专辑吧！
【蓝胖子编程教育简介】
蓝胖子编程教育，是一家面向青少年的编程教育平台。平台为全国青少年提供最专业的编程教育服务，包括提供最新最详细的编程相关资讯、最专业的竞赛指导、最合理的课程规划等。本平台利用趣味性和互动性强的教学方式，旨在激发孩子们对编程的兴趣，培养他们的逻辑思维能力和创造力，让孩子们在轻松愉快的氛围中掌握编程知识，为未来科技人才的培养奠定坚实基础。
欢迎扫码关注蓝胖子编程教育
