poj 1011 Sticks（クラシック検索問題：DFS＋剪定）

タイトル：出自http://poj.org/problem?id=1011
回転:http://www.qiyeku.com/xinwen/654439.html
説明：一定数量の小さい棒の長さを与えて、それは等長のいくつかの木の棒が勝手に切って得たのです。与えられた小さな棒のセットに対して、元の木の棒の最小長さを要求する。
考え方:
             1.この問題を見ると、棒を一つ一つ比較して、いくつかの原棒を回復できるかどうかを確認します。しかし、このように列挙するのは効率が低いです。
         2.ここでは深さ優先検索で（再帰的に実現する）速度を遍歴するのが速い。
         3.元の棒の長さが決まっていると仮定して、いくつかの棒でこのような棒を作ったら、他の原棒はもうこれらの使った棒でつなぎ合わせられなくなります。私たちはヴィシティー配列を設置して、これらがすでに「成功」した木の棒をマークすることができます。
         4.原木の棒の長さはどれぐらいですか？0からずっと後を試すことはないですよね？これは面倒くさいです。一番小さい原棒の長さは今の一番大きい棒より短くないです。一番長い原棒の長さは、すべての棒の長さよりも長くないです。これで範囲が確定します。
         5.私たちは深検索で何のパラメータを使いますか？
                    まず、ある可能性のある長さ（元の棒の長さ）を試してみます。このすべての棒で構成されているかどうかを確認します。このパラメータは必要です。lenと表記します。
                    そして、「成功」のたびに一本の小さな棒を受け取ると、それに応じて1.このパラメータが重要です。
                    また、私たちが試している原木の棒は価値を取ることができます。小さな木の棒を成功裏に受け取るたびに、もう一本の原木棒をつなぎ合わせるために必要な長さが減少します。これは検索過程でも知るべき量であり、0に減少すると、一本の原木棒のつなぎ合わせが完了すると説明し、再びlenに割り当てられ、次の木棒の捜索が行われる。このパラメータが同じであることが分かります。
        6.ある棒が成功して受信されたかどうかを確認するためには、前もってこの棒に加入した後、他の木の棒が成功したかどうかを予知しなければなりません。つまり、ある小さな棒を遍歴した時に、その後の木の棒を再帰的に検索してください。成功にマッチすれば、現在の木の棒を使用済みとしてマークして、直接に戻ることができます。;マッチできない場合は、この棒は現在使えないと説明し、次の検索用にマークをキャンセルします。現在の木の棒が使えない場合は、この棒と同じ長さの木の棒も使えなくなります。直接スキップします。また、この小さい棒の長さがちょうどレミセンの長さだと、後のマッチングができないと説明できます。このような適切な棒は受信されても手探りの成功に導くことができません。後ろの棒はさらに不可能です。直接に0に戻ります。また、len=remansuulen（これは新しい原棒です。まだマッチしていません。）マッチしているかどうかをあらかじめ判断した時にマッチしないと判断されましたが、これでは一致しないと説明されました。0に戻ります。
       7.remans＿ulen=0&&num=0で説明できる棒はもうなく、元の棒にするにはまだ必要な長さは0で、元の棒がすでに完全にこのすべての棒で連結されているということだけを表します。この時はlenに戻ります。この操作は関数の一番前に置くべきです。
      8.深度検索が完了したら、まだ打診に戻らないで成功しました。関数の最後には、この打診が失敗したとしか説明できません。直接に0に戻ります。
      9.使ったことがありますが、受信できなかった木の棒を再利用するために、関数では棒ごとに検索します。これらの網が抜けている木の棒が再利用されるかもしれません。
      10.元の棒の長さを変えて打診する時は、visitedを0にします。そうでないと前回の検索と混ざります。
 
コード：（ここで採用したdfsは、上に書いたnumではなく、sum再帰で残りの棒の和を表します。）

#include<iostream>
#include<algorithm>
#include<cstdlib>

using namespace std;

int temp[65];//      
int visited[65];//    
int n;

bool cmp(int a,int b)
{
	return  a>b; 
}
//len:        
//remain_len:                 
//sum:             
int dfs(int len,int remain_len,int sum)
{
	if(remain_len==0&&sum==0)return len;//    
	if(remain_len==0)remain_len = len;//          
	if(remain_len>sum)return 0;
	for(int i=0;i<n;i++){
		if(remain_len>=temp[i]&&visited[i]==0){
			visited[i] = 1;
			//           
			if(dfs(len,remain_len-temp[i],sum-temp[i]))
				return len;
			visited[i] = 0;
			if(temp[i]==remain_len||len==remain_len)break;
			//       temp[i]    ，            ，  
			if(temp[i]==temp[i+1])i++;
		}
	}
	return 0;
}

int main()
{
	int i,k;
	while(cin>>n,n){
		int sum = 0;
		for(i=0;i<n;i++){
			cin>>temp[i];
			sum += temp[i];
		}
		sort(temp,temp+n,cmp);

		for(i=temp[0];i<=sum;i++){
			memset(visited,0,sizeof(visited));/*              */
			if(sum%i==0){
				k = dfs(i,0,sum);
				if(k)break;
			}
		}
		cout<<k<<endl;
	}
	return 0;
}