【经典DFS】NYOJ-1058-部分和问题

【题目链接：NYOJ-1058】

　　看到题目难度是2，所以想也没想，直接循环比较。。。结果果然。。。是错的。

 1 #include<cstdio>
 2 #include<cstring>
 3 int main(){
 4     int n,k;
 5     int i,j;
 6     int a[22] = {0},num[22] = {0};
 7     scanf("%d%d",&n,&k);
 8     for(i = 0;i < n;i++)
 9         scanf("%d",&a[i]);
10     int ac = 0,xx = 0;
11     for(i = 0;i < n;i++){
12         int sum = 0;
13         for(j = i;j < n;j++){            
14             sum += a[j];
15             num[xx] = a[j];            
16             xx++;
17             if(sum == k){
18                 ac = 1;
19                 break;
20             }                        
21         }
22         if(ac == 1)
23             break;
24         else{
25             xx = 0;
26             memset(num,0,sizeof(num));
27         }
28     }
29     if(ac){
30         printf("YES
");
31         for(i = 0;i < xx;i++)
32             printf("%d ",num[i]);
33     }else{
34         printf("NO");
35     }
36     return 0;    
37 }

　　以上错误代码，就不回忆为啥错了。。。贴这儿供着吧。

这题的正确思路是运用DFS

　　详见：《挑战程序设计》 P30

 1 #include<cstdio>
 2 #include<stack> 
 3 #include<cstring>
 4 using namespace std;
 5 //部分和问题：
 6 const int maxn = 22;
 7 stack<int>v;
 8 int a[maxn];
 9 int n,m,i,j,k;
10 bool dfs(int i = 0,int sum = 0)     //已经从前i项得到了和sum,然后对于i项之后的进行分支
11 {
12     //停止条件 ：如果前n项都计算过了，则返回sum是否与k相等 
13     if(i==n) return sum==k;
14     //选择加或不加a[i]
15         //不加a[i]的情况 
16     if(dfs(i+1,sum)) return true;
17         //加上a[i]的情况 
18     if(dfs(i+1,sum+a[i])){
19         //若执行该条件，就说明该a[i]符合条件 
20         v.push(a[i]);//压栈 
21         return true;
22     } 
23     return false;           //无论是否加上a[i]都不能凑成k就返回false;
24 }
25 int main(){
26     while(~scanf("%d%d",&n,&k)){
27         for(int i = 0;i < n;i++){
28             scanf("%d",&a[i]);
29         }if(dfs()){
30             printf("YES
");
31             while(!v.empty()){
32                 int x = v.top();
33                 printf("%d ",x);
34                 v.pop();
35             }
36             printf("
");
37         }else
38             printf("NO
");        
39     }
40     return 0;
41 }

　　优化：

　　　　1.当然也可以用数组代替栈，时间消耗会短8个。

　　　　2.在状态转移时，如果sum > k，则不需要继续进行了。

　　　　（因为是递归，递归的机制就是从上到下，再从下到上返回，所以数组保存的顺序是反向的）

　　优化代码：

 1 #include<cstdio>
 2 #include<stack>
 3 using namespace std;
 4 stack<int>v; 
 5 const int maxn = 22;
 6 int a[maxn];
 7 //int sta[maxn]; 
 8 int n,m,k,pos;
 9 bool dfs(int i,int sum){
10     if(i==n) return sum==k;
11     else if(sum > k) return false; //剪枝（这么专业的名词也不知道用的对不对，反正就是优化了一下） 
12     if(dfs(i+1,sum)) return true;
13     if(dfs(i+1,sum+a[i])){
14         //sta[pos++] = a[i];        
15         v.push(a[i]);
16         return true;
17     } 
18     return false;          
19 }
20 int main(){
21     while(~scanf("%d%d",&n,&k)){
22         pos = 0;
23         for(int i = 0;i < n;i++){
24             scanf("%d",&a[i]);
25         }if(dfs(0,0)){
26             printf("YES
");
27 //            for(int i = pos - 1;i >= 0;i--)
28 //                printf("%d ",sta[i]);
29             while(!v.empty()){
30                 printf("%d ",v.top());
31                 v.pop();    
32             }                        
33             printf("
");
34         }else
35             printf("NO
");        
36     }
37     return 0;
38 }