poj1011，我自己的理解

這是我的第一篇文章，老實說，poj1011，是我第一次意識到我刷題是需要濃厚的演算法功底的，前幾題是我沒學過演算法，就根據我看書得來的經驗硬寫出來的，
原題鏈接：http://poj.org/problem?id=1011
半年前看見了這道題，我是確實沒有任何思路的，看到各路大神說什么dfs，咋也不知道是啥東西，百度了一下，說是深度優先搜索（depth first search），決定了，我得去學演算法和資料結構，
說來慚愧，學了半年演算法回來重新看這道題還是不會寫，我所接觸的dfs無非就是二分搜索樹的遍歷和圖論的尋路問題，但是又沒有深入去了解圖論的知識，所以又偷偷摸摸去看各路大神的代碼，原諒我天資愚鈍，他們寫的理論我是真看不懂，也不知道代碼內部原理到底是什么東西，所以我花了整整四天時間，梳理了一下這道題的dfs思想以及優化的關鍵（他們稱之為剪枝，謝天謝地，我的代碼終于被AC了，先上代碼，

#include<iostream>
#include<algorithm>
using namespace std;
int a[100],Min=0,n,sum;
bool visited[100];
bool cmp(int a,int b){
	return a>b;
}
bool dfs(int index,int cur,int total){
	if(total==Min)
		return true;
	for(int i=index;i<n;i++)
		if(!visited[i]&&a[i]<=cur){
			visited[i]=true;
			if(a[i]==cur){
				if(dfs(1,Min,total-a[i]))
					return true;
			}
			else if(dfs(i+1,cur-a[i],total-a[i]))
				return true;
			visited[i]=false;
			if(a[i]==cur)
				return false;
			if(cur==Min)
				return false;
			while(a[i]==a[i+1])
				i++;
		}
	return false;
}
int main(){
	while(cin>>n&&n!=0){
		sum=0;
		for(int i=0;i<100;i++)
			visited[i]=false;
		for(int i=0;i<n;i++){
			cin>>a[i];
			sum+=a[i];
		}
		sort(a,a+n,cmp);
		for(Min=a[0];Min<=sum;Min++){
			if(sum%Min==0&&dfs(0,Min,sum)){
				cout<<Min<<endl;
				break;		
			}	
		}
	}
}

由于木棒不能重復使用，我建立了一個bool型別全域變數的陣列visited來標記是否被用過，false表示沒有，true表示用過，a這個陣列是記錄每根木棒的長度，n是木棒的總個數，sum為木棒長度的總和，Min表示列舉出的長度，我們無法確定木棒的長度到底是多少，所以只能使用列舉法一一列舉，但是這是有方法的，由于喬治拿來的是>=1根的等長木棒并且所有的木棒要么是被切掉分出去的，要么就是原始的長度，所以不難想象，此時列舉出來的長度應當比木棒中最長的長，并且比木棒長度總和要短，同時滿足長度和sum%Min==0，或者說sum一定是Min的倍數，
首先應該做的是，對傳入的木棒長度進行一次排序，至于為什么要使用從大到小排序，我自己的理解就是若是從小到大排序的話，例如Min為10，假設此時a[0]等于1，那么剩下的長度就要是9，這種情況下排列組合的方式是很多的，但是如果從大到小排序的話，假設a[0]等于8，剩下的長度是2，能相加等于2的情況相比于9來說是要少很多的，這樣子做也是程式優化的一種辦法，
在dfs這個函式中，一共有三個引數，第一個是index，表示后面迭代的i是從幾開始的，第二個是cur，也就是剩下木棒的長度，再次舉剛剛的例子，假設a[0]等于8，剩下的長度是2，在呼叫下一次這個函式時，傳入的引數cur就應當是2，第三個引數total表示剩下的總長，其實我感覺這個思想和線段樹是十分相似的，遞回終止條件就是total與Min相等，此時就說明已經找到了一種方案能夠滿足所有的木棒都能被visited過，
現在說明一下dfs函式內部的思想，首先迭代的木棒一定是沒有被訪問過的，也就是!visited[i]，其次當前木棒的長度一定要<=cur才能符合要求，換句話說，就是我們想要找的木棒要比剩下的木棒長度短才能符合要求，此時呢，我們當前迭代的木棒就已經被訪問過了，也就是visited[i]=true;接下來我們要確定的事情就是，當前木棒的長度是否已經為0了，為0的話我們就要從頭開始迭代，并且當前木棒的長度就需要再次為Min了，不是的話我們就需要從i+1開始迭代，這是因為前面的木棒已經迭代過了，木棒的長度為cur-a[i]，這里total是需要一直-a[i]的，因為剩下的總長度一直在減少，
對于遞回演算法，我個人理解為廣義的和狹義的，廣義下dfs的完成的功能就是沒有被visited的木條能否符合Min的條件，而狹義的話我們就需要從他的實作一步步模擬計算（可能需要幾張草稿紙），我們可以這樣理解，當前的木棒已經和剩下木棒長度相等時，我們就從廣義的方面想沒有被visited的木條能否符合Min的條件，如果能就可以直接return true了，不能的話不能直接return false，因為我們的i還需要往下迭代尋找符合的長度，當我們執行到visited[i]=false的時候也就意味著沒有return true，換句話說就是當前列舉的i不可行，那么當什么時候我們不需要往下繼續列舉直接return false呢？這也是剪枝的重要程序，
第一，a[i]==cur時，為什么呢，因為我們之前已經執行了

			if(a[i]==cur){
				if(dfs(1,Min,total-a[i]))
					return true;

但是并沒有return true，換句話說，剩下沒有被visited過的木棒不符合條件，我們a[i]==cur時，就可以看成被訪問過的木棒已經沒了，也就是形成了一個形式一樣的子問題，例如：5 5 5 2 2 2 1 1 1，我們將 5和1訪問完了后，可以看成此時題目是5 5 2 2 2 1 1的子問題，如果子問題行不通的話，我們總問題下這種列舉的情況是不肯定成立的，
第二，cur=Min時，我們每列舉的第一根木棒時，若在搜索完所有a[]后都無法組合，那么就可以直接return false，這是因為我們每一根木棒都需要用上，當cur=Min，就說明我們此時列舉的那根木棒是無法用上的，這例列舉是不可行的，
最后一個優化的思路就是，當下一根木棒和當前木棒長度相等時，由于當前木棒此時列舉不可行，所以下一根也是不可行的，
其實我大多數時間都花在為什么會有列舉不可行卻不直接return false的原因的，我想了好久，終于明白若是i迭代程序中，原本和別的木棒組成一根木棒的被當前的木棒搶占了并且正好組合成功，剩下的木棒就無法成功組合了，
接下來，我用我想出來的例子來說明下：10 7 7 7 4 4 3 2 1
這種情況正確的組合應當是10 3 2; 7 7 1; 7 4 4;
但是我們第一次遞回的時候10直接流氓一樣把4和1搶走了，導致剩下的木棒無法正確合成15，由于下面的遞回呼叫return了0，也就是說明10和4根本不是一對，10再也不敢和4在一起了，就去往下找3，此時才是正確的組合方式，
文章的最后呢，由于我只是一名普通二本的大二學生，我的眼界十分有限，如果我有什么說錯的地方，希望你們能夠幫我糾正一下錯誤，感謝你們能夠有耐心地看完我的這篇文章，祝愿你們的代碼沒有bug！