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

2019-11-10 16:45:21

字體：大中小

供稿：網(wǎng)友

HDOJ(HDU).1258 Sum It Up (DFS) [從零開始DFS(6)]

點我挑戰(zhàn)題目

從零開始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)] —小結(jié)：做DFS題目的關(guān)注點 HDOJ(HDU).1035 Robot Motion [從零開始DFS(4)]—DFS題目練習(xí) HDOJ(HDU).1241 Oil Deposits(DFS) [從零開始DFS(5)] —DFS八向搜索/雙重for循環(huán)遍歷 HDOJ(HDU).1258 Sum It Up (DFS) [從零開始DFS(6)] —DFS雙重搜索/去重技巧 HDOJ(HDU).1045 Fire Net [從零開始DFS(７)]—DFS練習(xí)/check函數(shù)的思想

題意分析

每組數(shù)據(jù)給出要湊出的目標(biāo)數(shù)字num和數(shù)字個數(shù)n，然后依次給出n個數(shù)字。要求從n個數(shù)字中選出若干個數(shù)字，是的數(shù)字之和為nun。重復(fù)的組合只輸出一次。

和之前做過的選數(shù)字的題目類似，也可以采用DFS的思想來做。這道題與 HDOJ.1342 Lotto [從零開始DFS(0)]及其的相似：每個數(shù)字有2種選擇，選/不選，只要我選擇的這些數(shù)字的和為num就行了。但是不難想到會有重復(fù)的組合出現(xiàn)，例如給出的樣例3：

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

要求從12個數(shù)字中選擇出若干數(shù)字使得總和為400，我們可以發(fā)現(xiàn)選擇6個50和4個25即可。那么若按照HDOJ.1342的思想，選/不選，問題就會出現(xiàn)：要從6個25中選4個25，會有C（6,4）中情況，也就是說最后的結(jié)果會多出11組相同的解。這顯然不符合題意。問題的關(guān)鍵在于如何去重，最先想到也是最容易想到的就是把每組解保存下來，如果遇到重復(fù)的只輸出一組即可。很明顯這種方法實現(xiàn)起來耗費的工程量是巨大的，非常麻煩。回到DFS的核心：遞歸。我們對于遞歸做出一些約束，當(dāng)滿足一定條件時，下面搜索的解會造成重復(fù)，就終止遞歸。這樣得到的解，均是非重復(fù)的。關(guān)鍵就是找到這樣的條件，或者說為遞歸創(chuàng)造這樣的條件。

上代碼。

代碼總覽

/* 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; //選擇的數(shù)的位置超出數(shù)據(jù)范圍 b[depth] = a[pos]; dfs(depth+1,sum+a[pos],pos+1); while(pos+1<n&&a[pos] == a[pos+1]) pos++;//關(guān)鍵 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的辦法（即選/不選的思想），解決此題。遞歸邊界：當(dāng)數(shù)字的和為num時，或者和超出了num，或者要選擇的數(shù)字位置超出了n，終止搜索。關(guān)鍵是下面這幾句。

dfs(depth+1,sum+a[pos],pos+1); while(pos+1<n&&a[pos] == a[pos+1]) pos++;//關(guān)鍵 dfs(depth,sum,pos+1);

首先是默認選擇了pos這個位置的數(shù)字然后進行dfs。下面一個while循環(huán)表示如果下一個待選數(shù)字和本位置的待選數(shù)字一樣的話，就跳過，一直跳到下一個待選數(shù)字不同的位置。如樣例3：

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

就會從第一個50一直跳到最后一個50（下一個數(shù)字是25）。貌似看起來得不到正確結(jié)果，當(dāng)然在第一層dfs不選擇50的情況是沒有正確解的。不放我們看一下下一層dfs，即選擇了第一個50后的dfs。

進入第二層dfs依舊會有2種選擇，要么選擇第二個50，要么后續(xù)的50一個都不選。當(dāng)然這時候一個50都不選的情況也是沒有正確解的，繼續(xù)看第三層。

進入第三層dfs還是會有2種選擇，要么選擇第三個50，要么后續(xù)的50一個都不選。但讓后續(xù)50一個都不選的情況也沒有正確解。

…………

依次類推，不難發(fā)現(xiàn)，這條while語句的作用就是：營造單一的選1個50，選2個50，選3個50這樣的情況，從而避免了重復(fù)解的出現(xiàn)。

上一篇：Frame和JFrame代碼比較

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