首页 > 代码库 > 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 }
16级第四周寒假作业A题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。