深度搜索和宽度搜索对立，宽度搜索是横向搜索（队列实现），而深度搜索是纵向搜索（递归实现）；
看下面这个例子：
现在需要驾车穿越一片沙漠，总的行驶路程为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 即可得出结果；
具体实现代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 |
#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 ;} |
很高兴总算找到答案了，但是不要忘了这个数据可能会很大，如果还用这个方法肯定会超时，如果一个算法速度达不到，这个算法是没有多大意义的。
那我们下面应该想想能不能用对程序进行优化，看到上面是不是有很多地方都是重复计算了，一般可以用多消耗一些内存换取程序运行的时间；
观察发现，当带四桶相同的油，多算了好多，既然是深度搜索，应该一直往深度探索，所以以上程序可修改为：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 |
#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 ;} |
就算如此优化，还是避免不了超时的结果，那还应该如何优化才能达到想要的结果呢，结果发现，还存在可以优化的地方，如果一桶汽油就可以跑完全程，那样的汽油就应该抛弃，通过先前对汽油种类排序，最后留下来的都是一桶跑不完全程的，当全程不能够分成四份时，那么同一种汽油最多取三桶；
通过分析再次对上面程序就行优化得到下面程序：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 |
#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 则代表存在 ；
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 |
#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,布布扣,bubuko.com
原文：http://www.cnblogs.com/scottding/p/3661157.html