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

2019-11-10 17:27:45

字體：大中小

來源：轉載

供稿：網友

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組相同的解。這顯然不符合題意。問題的關鍵在于如何去重，最先想到也是最容易想到的就是把每組解保存下來，如果遇到重復的只輸出一組即可。很明顯這種方法實現起來耗費的工程量是巨大的，非常麻煩?；氐紻FS的核心：遞歸。我們對于遞歸做出一些約束，當滿足一定條件時，下面搜索的解會造成重復，就終止遞歸。這樣得到的解，均是非重復的。關鍵就是找到這樣的條件，或者說為遞歸創造這樣的條件。

上代碼。

代碼總覽

/* 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這樣的情況，從而避免了重復解的出現。

上一篇：HDOJ(HDU).1241 Oil Deposits(DFS)

下一篇：bzoj4542 [Hnoi2016]大數