首页 > 代码库 > 16级第四周寒假作业A题

16级第四周寒假作业A题

T^T找数字

TimeLimit:1000MS  MemoryLimit:256MB
64-bit integer IO format:%I64d
Problem Description

有一天,T^T来到了师大比赛,看上了师大的ACMer小彩,于是他就跑上去想跟人家搭讪,可是呢,这时候,小彩遇到了一个问题,小彩说,你要是帮我解决了这个

问题,我就把我的手机号给你,T^T一听,顿时乐了起来,这不是我的强项嘛,于是就让小彩说了:

   给定整数a1,a2,....,an,判断是否可以从中选出若干数(取数的数目 > 0),使它们的和恰好为k

Input

输入有多组数据,输入的第一行有两个数,分别为n,k(1 <= n <= 20,-10^8 <= k <= 10^8,不考虑k = 0的情况);

第二行是n个数,分别是a1,a2,a3,...,an(-10^8 <= ai <= 10^8)

 

Output

能找到这样的若干个数的和为k(由于oj无法特判,因此输入保证只有一组这样的数),则输出YES,并且按照顺序输出这些数,否则的话,输出NO

 

SampleInput
4 13
1 2 4 7
4 15
1 2 4 7
SampleOutput
YES
2 4 7
NO

思路:这一题其实就是入门的搜索题。进入正题,我们先用sum来记录这些数的和,用数组来存给定的n个数,显然,一开始的时候,sum的值为0.然后我们考虑给定的这n个数,对于每个

数,只有两种状态,要么取这个数,要么不取,因为n<=20,我们就直接遍历所有的状态,因为只有两种状态,所以素有状态所形成的就是二叉树,如下图所示

技术分享(我就不画出所有的状态了)

在暴力遍历所有的状态之后,当匹配到sum=k的时候,我们就返回根节点,在返回根节点的时候我们就用栈存储符合条件的数,以便于我们有序的输出。

然后就是进行剪枝操作,比如当sum>k的时候,我们就可以略过该节点,以免进行不必要的操作;

大致的内容就是这样,放出我的DFS代码给大家作为参考,具体的可以看我代码上的注释

技术分享
 1 bool DFS(int i,int sum)//i表示的是当前考虑的是哪个数,sum表示当前的和
 2 {
 3     if(sum>k)
 4         return false;//剪枝
 5     if(i==n)//如果前n项均已经计算过,那么判断此时sum的值是否与k相等,并回溯至上一层 
 6         return k==sum;
 7         if(DFS(i+1,sum+a[i]))//加上a[i]的情况
 8         {
 9             s.push(a[i]);
10             return true;
11         }
12         if(DFS(i+1,sum))//不加上a[i]的情况
13             return true;
14         return false;
15 }
View Code

 

 

 

 

16级第四周寒假作业A题