HDOJ(HDU).1258 Sum It Up (DFS)

2019-11-10 16:45:21

字体：大中小

来源：转载

供稿：网友

HDOJ(HDU).1258 Sum It Up (DFS) [从零开始DFS(6)]

点我挑战题目

从零开始DFS HDOJ.1342 Lotto [从零开始DFS(0)] — DFS思想与框架/双重DFS HDOJ.1010 Tempter of the Bone [从零开始DFS(1)] —DFS四向搜索/奇偶剪枝 HDOJ(HDU).1015 Safecracker [从零开始DFS(2)] —DFS四向搜索变种 HDOJ(HDU).1016 PRime Ring Problem (DFS) [从零开始DFS(3)] —小结：做DFS题目的关注点 HDOJ(HDU).1035 Robot Motion [从零开始DFS(4)]—DFS题目练习 HDOJ(HDU).1241 Oil Deposits(DFS) [从零开始DFS(5)] —DFS八向搜索/双重for循环遍历 HDOJ(HDU).1258 Sum It Up (DFS) [从零开始DFS(6)] —DFS双重搜索/去重技巧 HDOJ(HDU).1045 Fire Net [从零开始DFS(７)]—DFS练习/check函数的思想

题意分析

每组数据给出要凑出的目标数字num和数字个数n，然后依次给出n个数字。要求从n个数字中选出若干个数字，是的数字之和为nun。重复的组合只输出一次。

和之前做过的选数字的题目类似，也可以采用DFS的思想来做。这道题与 HDOJ.1342 Lotto [从零开始DFS(0)]及其的相似：每个数字有2种选择，选/不选，只要我选择的这些数字的和为num就行了。但是不难想到会有重复的组合出现，例如给出的样例3：

400 12 50 50 50 50 50 50 25 25 25 25 25 25

要求从12个数字中选择出若干数字使得总和为400，我们可以发现选择6个50和4个25即可。那么若按照HDOJ.1342的思想，选/不选，问题就会出现：要从6个25中选4个25，会有C（6,4）中情况，也就是说最后的结果会多出11组相同的解。这显然不符合题意。问题的关键在于如何去重，最先想到也是最容易想到的就是把每组解保存下来，如果遇到重复的只输出一组即可。很明显这种方法实现起来耗费的工程量是巨大的，非常麻烦。回到DFS的核心：递归。我们对于递归做出一些约束，当满足一定条件时，下面搜索的解会造成重复，就终止递归。这样得到的解，均是非重复的。关键就是找到这样的条件，或者说为递归创造这样的条件。

上代码。

代码总览

/* Title:HDOJ.1258 Author:pengwill Date:2017-2-8*/#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int num,n,pos;int a[15],b[15];bool judge = false;void output(int depth){ for(int i =0 ;i< depth; ++i) if(!i) printf("%d",b[i]); else printf("+%d",b[i]); printf("/n");}void dfs(int depth,int sum,int pos){ if(sum == num) {judge = true;output(depth); return;} if(sum>num) return;// 超出了终止递归 if(pos>=n) return; //选择的数的位置超出数据范围 b[depth] = a[pos]; dfs(depth+1,sum+a[pos],pos+1); while(pos+1<n&&a[pos] == a[pos+1]) pos++;//关键 dfs(depth,sum,pos+1);}int main(){ //freopen("in.txt","r",stdin); while(scanf("%d%d",&num,&n) && num){ printf("Sums of %d:/n",num); for(int i = 0; i<n; ++i) scanf("%d",&a[i]); judge = false; dfs(0,0,0); //output if(judge == false) printf("NONE/n"); } return 0;}

还是按照 HDOJ.1342 Lotto [从零开始DFS(0)]中写到的双重DFS的办法（即选/不选的思想），解决此题。递归边界：当数字的和为num时，或者和超出了num，或者要选择的数字位置超出了n，终止搜索。关键是下面这几句。

dfs(depth+1,sum+a[pos],pos+1); while(pos+1<n&&a[pos] == a[pos+1]) pos++;//关键 dfs(depth,sum,pos+1);

首先是默认选择了pos这个位置的数字然后进行dfs。下面一个while循环表示如果下一个待选数字和本位置的待选数字一样的话，就跳过，一直跳到下一个待选数字不同的位置。如样例3：

400 12 50 50 50 50 50 50 25 25 25 25 25 25

就会从第一个50一直跳到最后一个50（下一个数字是25）。貌似看起来得不到正确结果，当然在第一层dfs不选择50的情况是没有正确解的。不放我们看一下下一层dfs，即选择了第一个50后的dfs。

进入第二层dfs依旧会有2种选择，要么选择第二个50，要么后续的50一个都不选。当然这时候一个50都不选的情况也是没有正确解的，继续看第三层。

进入第三层dfs还是会有2种选择，要么选择第三个50，要么后续的50一个都不选。但让后续50一个都不选的情况也没有正确解。

…………

依次类推，不难发现，这条while语句的作用就是：营造单一的选1个50，选2个50，选3个50这样的情况，从而避免了重复解的出现。

上一篇：Frame和JFrame代码比较

下一篇：变通思想： 01背包