先来审题,主要有以下几个条件:
酸度求乘积,苦度求和,两者相减的值最小(当然是绝对值)。
下面附上AC代码:
#include<bits/stdc++.h> //万能头文件
using namespace std; //命名空间
int n,s[15],b[15]; //s为酸度,b为苦度 。
int vis[15]; //表示访问的第几组食材。
int S=1,B=0,minn=2147483647;
//S为酸度乘积,B为苦度之和,minn赋int最大值。
void dfs(int x){
if(abs(S-B)<minn&&x!=0) minn=abs(S-B);
//至少要一种,所以x!=0,差小于minn,就对minn重新赋值。
if(minn==0)return ;
//因为不可能比零小,特判优化算法。
if(x==n)return ; //食材选满,结束这一层,倒推(回溯)。
for(int i=1;i<=n;i++){
if(!vis[i]){ //食材还未被访问(使用)过。
S*=s[i];B+=b[i];vis[i]=1;
//记录酸度,苦度,同时占位(食材已被使用) 。
dfs(x+1);
//使用下一种食材,食材数量+1。
S/=s[i];B-=b[i];vis[i]=0;
//还原酸度,苦度,同时取消占位。
}
}
}
int main(){
cin>>n; //输入不说多少。
for(int i=1;i<=n;i++){
cin>>s[i]>>b[i]; //每组食材对应的酸度和苦度。
}
dfs(0); //从零种食材开始搜索。
cout<<minn; //输出搜索得到的最小值。
return 0;//完美结束。
}