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

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(7)]—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这样的情况,从而避免了重复解的出现。

上一篇:Flex 学习笔记 ComboBox内容框宽度


下一篇:HDOJ(HDU).1166 敌兵布阵 (ST 单点更新 区间求和)