Depth-First Search

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

看下面这个例子：

　　现在需要驾车穿越一片沙漠，总的行驶路程为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<iostream>

#include<string.h>

#include<string>

#include<algorithm>

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<iostream>

#include<string.h>

#include<string>

#include<algorithm>

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<stdio.h>

#include<string.h>

#include<algorithm>

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<n;i++)

        for(j=1;j<=m;j++)

            dfs(i+1,count+j,sum+j*a[i]);

}

int main()

{

    int t;

    int i,j;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d%d",&l,&x,&n);

        l=l-x;

        for(i=0;i<n;i++)

            scanf("%d",&a[i]);

        sort(a,a+n);

        for(i=0;i<n;i++)

            if(a[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<iostream>

#include<string>

#include<string.h>

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 ;

}

巴特西

Depth-First Search

最新文章

热门文章