深度搜索和宽度搜索对立，宽度搜索是横向搜索（队列实现），而深度搜索是纵向搜索（递归实现）；

看下面这个例子：

　　现在需要驾车穿越一片沙漠，总的行驶路程为L。小胖的吉普装满油能行驶X距离，同时其后备箱最多能放下四桶油。在起点有N种汽油，每种汽油都有无限桶，一桶能行驶距离Ai。现在小胖想知道：能不能恰好带四桶油，再加上出发前装满的油，使得恰好能行驶L距离。

两个 恰好 使得这道题的难度增加；

如何才能做到恰好？ 动态规划 还是 搜索？

先看看搜索行不行

限制条件是：“恰好四桶油”，“恰好行驶距离为L” 

那就一个一个的试试，深搜一把试试看

bool flag = false ;

void dfs( int tong , int s )　　{

　　if(tong > 4  || s > L)

　　　　return ;

　　if(tong == 4 && s == L)　　{

　　　　flag = true ;

　　　　return ;

　　}

　　for(int i = 1 ; i <= n ; i++ )　　// n 为汽油种类

　　　　for(int j = 1 ; j <= 4 ; j++)

　　　　　　dfs(tong + j , s + a[i] * j ) ;

}

如果能够找到 flag 就为 true ；

判断 flag 即可得出结果；

具体实现代码如下：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std ;int a[1005] ;int L , X , N ;int ans ;void dfs(int a1 , int sum)	{	if(a1 > 4 || sum > L - X)		return ;	if(a1 == 4 && sum == L - X)	{		ans = 1 ;		return ;	}	for(int i = 1 ; i <= N ; i++)		for(int j = 1 ; j <= 4 ; j++)			dfs(a1+j , sum + a[i] * j ) ;}int main()	{	int n ; 	cin >> n ;	while(n--)	{		cin >> L >> X >> N ;		memset(a,0,sizeof(a[0])) ;		for(int i = 1 ; i <= N ; i++)			cin >> a[i] ;		sort(a+1,a+1+n) ;		ans = 0 ;		dfs(0,0) ;		if(ans)			cout << "Yes" << endl ;		else			cout << "No" << endl ;	}	return 0 ;}
        
       
      
     

　　

很高兴总算找到答案了，但是不要忘了这个数据可能会很大，如果还用这个方法肯定会超时，如果一个算法速度达不到，这个算法是没有多大意义的。

 

那我们下面应该想想能不能用对程序进行优化，看到上面是不是有很多地方都是重复计算了，一般可以用多消耗一些内存换取程序运行的时间；

 

观察发现，当带四桶相同的油，多算了好多，既然是深度搜索，应该一直往深度探索，所以以上程序可修改为：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std ;int a[1005] ;int L , X , N ;int ans ;void dfs(int i ,int a1 , int sum)	{	if(a1 > 4 || sum > L - X)		return ;	if(a1 == 4 && sum == L - X)	{		ans = 1 ;		return ;	}	for( ; i <= N ; i++)		for(int j = 1 ; j <= 4 ; j++)			dfs(i+1,a1+j , sum + a[i] * j ) ;}int main()	{	int n ; 	cin >> n ;	while(n--)	{		cin >> L >> X >> N ;		memset(a,0,sizeof(a[0])) ;		for(int i = 1 ; i <= N ; i++)			cin >> a[i] ;		sort(a+1,a+1+n) ;		ans = 0 ;		dfs(1,0,0) ;		if(ans)			cout << "Yes" << endl ;		else			cout << "No" << endl ;	}	return 0 ;}
        
       
      
     

　　

就算如此优化，还是避免不了超时的结果，那还应该如何优化才能达到想要的结果呢，结果发现，还存在可以优化的地方，如果一桶汽油就可以跑完全程，那样的汽油就应该抛弃，通过先前对汽油种类排序，最后留下来的都是一桶跑不完全程的，当全程不能够分成四份时，那么同一种汽油最多取三桶；

通过分析再次对上面程序就行优化得到下面程序：

#include
     
      #include
      
       #include
       
        using namespace std;int a[1002];int l,x,n,m;int flag;void dfs(int i,int count,int sum){    int j;    if(count>4||sum>l||flag)        return;    if(count==4&&sum==l)    {        flag=1;        return ;    }    for(;i
        
         =l)   //若第a[i]种汽油，一桶的行驶路程不小于l-x，后面的搜索情况不能满足题意，直接舍弃后面的数据            {                n=i;                break;            }        m=4;        if(l%4!=0)  //若l-x不能被4整除，每种汽油最多带3桶，可能满足题意            m=3;        flag=0;        dfs(0,0,0);        if(flag)            printf("Yes\n");        else            printf("No\n");    }    return 0;}
        
       
      
     

　　

下面介绍一种用动态规划解答方案：

用 dp[ i ][ j ] 代表 带 i 桶汽油，恰好能行驶 j 公里，如果 dp[ 4 ][ L ] = true 则代表存在 ；

#include
     
      #include
      
       #include
       
        using namespace std ;int main()	{	int n ;	cin >> n ;	while(n--)	{		bool dp[6][1005] ;      // dp[i][j]  带 i 桶汽油，恰好能行驶 j 公里		memset(dp,false,sizeof(dp)) ;		int L , X , N ;		cin >> L >> X >> N ;		int a[1005];		for(int ii = 1 ; ii <= N ; ii++)			cin >> a[ii] ;		L = L - X ;		dp[0][0] = true ;   //  带 0 桶汽油 ， 恰好行驶 0 公里		for(int i = 0 ; i <= L ; i++)             // 控制条件有两个时，主要判断哪个在前，哪个在后			for(int j = 0 ; j <= 4 ; j++)	{				if(dp[j][i])					for(int k = 1 ; k <= N ; k++)	{						if(i + a[k] <= L )							dp[j+1][i+a[k]] = true ;	// 为动态变量赋值					}			}		if(dp[4][L])			cout << "Yes" << endl ;		else			cout << "No" << endl ;	}	return 0 ;}