经典的深搜
关于红皮书的剪枝，我是这么理解的：left==len，即a木棍放在第一个位置并且失败的情况，假如可以尝试后面的情况，并且成功，那么a必然在某个木棍的中间部分，那a也可以移到第一个位置，则和a失败的情形矛盾，所以没有必要再去尝试，跳出。stick[i]==left，即a木棍放在其中一个木棒的最后一个位置并且失败，如果尝试后面的更短的木棍b，假如成功，既然成功了，则可以用那些短的木棍与a交换，那么又与之前的结论矛盾了，所以也没有必要搜下去。
#include<iostream> using namespace std; #include<cstdlib> int stick[65],visited[65]; bool dfs(int total,int unused,int left,int len) { int i; if(unused==0&&left==0) return true; if(left==0) left=len; for(i=0;i<total;i++) { if(visited[i]) continue; if(stick[i]>left) continue; visited[i]=1; if(dfs(total,unused-1,left-stick[i],len)) return true; visited[i]=0; if(stick[i]==left||left==len) break; } return false; } int cmp(const void *p,const void *q) { return *(int *)q-*(int *)p; } int main() { int n,i,aver,m; while(scanf("%d",&n),n) { m=0; for(i=0;i<n;i++) { scanf("%d",stick+i); m+=stick[i]; } memset(visited,0,sizeof(visited)); qsort(stick,n,sizeof(stick[0]),cmp); for(aver=stick[0];aver<=m;aver++) { if(m%aver) continue; if(dfs(n,n,0,aver)) { printf("%d/n",aver); break; } } } return 0; }
