POJ 1011 拯救少林神棍（Sticks)

Description

喬治拿來一組等長的木棍，將它們隨機地砍斷，使得每一節木棒的長度都不超過50個長度單位，然后他又想把這些木棍恢復到為裁截前的狀態，但忘記了初始時有多少木棍以及木棍的初始長度，請你設計一個程式，幫助喬治計算木棍的可能最小長度，每一節木棒的長度都用大于零的整數表示，

Input

輸入包含多組資料，每組資料包括兩行，
第一行是一個不超過64的整數，表示砍斷之后共有多少節木棒，
第二行是截斷以后，所得到的各節木棒的長度，
在最后一組資料之后，是一個零，

Output

為每組資料，分別輸出原始木棍的可能最小長度，每組資料占一行，

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6
5

AC代碼

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
using namespace std;
int N, L;//定義木棒數目和假設棍子的長度 
vector<int> anLength;//用于存放所有木棒長度 
int anUsed[65];//是否用過的標記且全域變數自動初始化為0即木棒未使用過 
int nLastStickNo;//用于儲存最近那根拼上去的木棒下標 
bool DFS(int nUnusedSticks, int nLeft);

int main()
{
	while(1) 
	{
		cin >> N;//輸入所有木棒根數 
		if( N == 0 ) break;
		int nTotalLen = 0;//所有木棒總長度 
		anLength.clear();
		for(int i = 0;i < N; i++) 
		{
			int n;//單根木棒長度 
			cin >> n;
			anLength.push_back(n);
			nTotalLen += anLength[i];
		}
		sort(anLength.begin(),anLength.end(),greater<int>()); //要使木棒從長到短進行嘗試，好比天平上稱物品,加砝碼也是從大到小試 
		for(L = anLength[0];L <= nTotalLen / 2; L++) //從最長的木棒開始從長到短依次列舉木棍長度L
		{
			if(nTotalLen % L)	continue;
//能整除代表你可以拼成若干組等長木棍，不能整除代表你可能會拼得幾根等長的棍子，但最后總會有木棒剩下  
			memset(anUsed, 0, sizeof(anUsed));//初始化anUsed陣列元素為0
			if(DFS(N, L)) //s根可用的木棒,L為假設的木棍長度 
			{
				cout << L << endl;
				break;
			}
		}
		if(L > nTotalLen / 2) cout << nTotalLen << endl;
//如果列舉出的木棍長度大于所有木棒總長度的一半那么就沒法拼成兩根或更多木棍，故此木棒總長度便是最短的木棍長度 
	} 
	return 0;
}

bool DFS(int nUnusedSticks, int nLeft) 
{
// nLeft表示當前正在拼的棍子和 L 比還缺的長度
	if(nUnusedSticks == 0 && nLeft == 0) 
	return true;//沒有木棒剩下且沒有哪根棍子缺長度，任務完成！ 
	if(nLeft == 0) //木棒剩下且沒有哪根棍子缺長度，證明一根木棍剛剛拼完，再新拼一根 
	nLeft = L; //開始拼新的一根木棍 
	
	//剪枝4： 
	int nStartNo = 0;
	if(nLeft != L) //拼這根棍子的木棒不是第一根木棒 
	nStartNo = nLastStickNo + 1;//從上一次選取的后面進行選取，保證了拼木棍時木棒先長后短 
	
	for(int i = nStartNo;i < N; i++) 	
	{
		if(!anUsed[i] && anLength[i] <= nLeft) 
		{
			//剪枝1： 
			if(i > 0)
			{
				if(anUsed[i-1] == false && anLength[i] == anLength[i-1])
				continue;//若木棒之前一根木棒用過或和前一根等長那么就不用這根木棒
			}	 
			anUsed[i] = 1;
			nLastStickNo = i;
			if (DFS(nUnusedSticks - 1, nLeft - anLength[i]))
			return true;
			else{
				anUsed[i] = 0;//說明本次不能用這第i根木棒但這第i根以后還有用
				
				//剪枝2和3： 
				if(nLeft == L||anLength[i] == nLeft) return false;
			//2：這第i根木棒是這根棍子的第一根木棒，但anUse[i]=0表示這第i根木棒不能用,故拼接失敗  
			//3：這第i根木棒是這根棍子最后一根木棒，但anUse[i]=0表示這第i根木棒不能用,故拼接失敗 
		    }
	    }
	}
	return false;//所有的木棒都拿來試過了，但棍子長度不合理故return false 
}

DEV C++測驗結果：

演算法決議

DFS的基本遞推關系：

bool DFS(int R, int M)
{
	if( R == 0 && M == 0)
	return true; //拼接任務完成
	//若能找到一根長度不超過M的木棒, 假設長為S，拼在當前棍子上,然后:
	DFS(R – 1,M - S);
	//如果找不到：
	return false;
}

剪枝 1

不要在同一個位置多次嘗試相同長度的木棒，
即：如果某次拼接選擇長度為S 的木棒，導致最終失敗，則在同一位置嘗試下一根木棒時，要跳過所有長度為S 的木棒，

剪枝 2

如果由于以后的拼接失敗，需要重新調整第i根棍子的拼法，則不會考慮替換第i根棍子中的第一根木棒（換了也沒用），如果在不替換第一根木棒的情況下怎么都無法成功，那么就要推翻第 i ? 1 i-1 i?1根棍子的拼法，如果不存在第 i ? 1 i-1 i?1根棍子，那么就推翻本次假設的棍子長度，嘗試下一個長度，
若棍子 i i i 如下拼法導致最后不能成功:

可以考慮把木棒2,3換掉重拼棍子i,但是把2，3都去掉后，換1是沒有意義的，

為什么替換第i根棍子的第一根木棒是沒用的？

因為假設替換后能全部拼成功，那么這被換下來的第一根木棒，必然會出現在以后拼好的某根棍子k中，那么我們原先拼第i根棍子時, 就可以用和棍子k同樣的構成法來拼，照這種構成法拼好第i根棍子，繼續下去最終也應該能夠全部拼成功，

剪枝 3

不要希望通過僅僅替換已拼好棍子的最后一根木棒就能夠改變失敗的局面，

假設由于后續拼接無法成功，導致準備拆除的某根棍子 i i i 如下：

將 3 拆掉，留下的空用其他短木棒來填是徒勞的！

假設替換3后最終能夠成功，那么3必然出現在后面的某個棍子 k k k 里，將棍子 k k k 中的3和棍子 i i i 中用來替換3的幾根木棒對調，結果當然一樣是成功的，這就和i原來的拼法會導致不成功矛盾

剪枝 4

拼每一根棍子的時候，應該確保已經拼好的部分，長度是從長到短排列的，即拼的程序中要排除類似下面這種情況：

未完成的棍子 i i i

木棒3 比木棒2長，這種情況的出現是一種浪費，因為要是這樣往下能成功，那么2, 3 對調的拼法肯定也能成功，由于取木棒是從長到短的，所以能走到這一步，就意味著當初將3放在2的位置時，是不成功的
排除辦法：每次找一根木棒的時候，只要這不是一根棍子的第一條木棒，就不應該從下標為0的木棒開始找，而應該從剛剛(最近）接上去的那條木棒的下一條開始找，這樣，就不會往2后面接更長的3了

為此，要設定一個全域變數 nLastStickNo ，記住最近拼上去的那條木棒的下標，