Question

什么情况下用dfs什么情况下用bfs？

最小差mindif
☆问题描述：
现在要配制某种特殊液体，它有A、B两种属性值。在配制时，有N个原材料液体，每个原材料也有同样的两种属性Ai、Bi，如果要选择多个原材料放在一起，则混合后的液体的两种属性值分别是Ai的积、Bi的和。
现在要求你从中选择其若干个（至少1个）原材料配制成品，使得最后的液体中两种属性值相差最小，即abs(A-B)最小。
☆输入（mindif.in）
第一行一个整数N表示原材料的个数.下面N行,每行两个正整数，每行两个正整数，分别表示相应原材料的两种属性值Ai、Bi。
☆输出（mindif.out）
一个整数，即最小的差值。
☆输入、输出样例：
mindif.in mindif.out
4
1 7
2 6
3 8
4 9 1
说明：选后3个，A=2×3×4=24，B=6+8+9=23。
☆数据说明：
1、1≤N≤10；
2、最终结果不超过1000 000 000。
3、时间限制：1s；内存限制：128M。
程序：
#include<iostream>
using namespace std;
struct xx{
int a,b;
}t[10];
int n,i,m;
void dfs(int i,int a,int b){
if(i==n){if(abs(a-b)<m&&b)m=abs(a-b);return;}
dfs(i+1,a,b);
dfs(i+1,a*t[i].a,b+t[i].b);
}
int main(){
freopen("mindif.in","r",stdin);
freopen("mindif.out","w",stdout);
cin>>n;m=1000000000;
for(i=0;i<n;i++)cin>>t[i].a>>t[i].b;
dfs(0,1,0);
cout<<m;
return 0;
}
解空间是什么？为什么有两次递归：dfs(i+1,a,b); dfs(i+1,a*t[i].a,b+t[i].b);分别是什么意思？

Answer 1

ryrtr