问题重述：
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
思路：
这是一个经典搜索题和剪枝例题。剪枝的空间很大，剪枝前写下朴素的搜索框架（黑字部分），枚举原始木棍的长度及由那些小木棍组合。原始木棍长度一定是小木棍总长度的约数，因此可以减少枚举量。
1.看到这个题，就是要把小棒一个个进行比较，看能不能恢复若干个原棒。但这样枚举效率太低。
2.这里用深度优先搜索来遍历（递归实现）速度较快。
3.假设原始木棒的长度已定，那么由若干小棒来组成一根这样的棒后，其它的原棒将不再由这些已经用过的小棒来拼接了。我们可以设置visited数组来标记这些已经“成功”拼接的木棒，而不是已经用过的木棒。
4.那么原始木棒长度有多长，不至于从0一直往后试探吧？这样太麻烦。因为长度最小的原棒，它的长度不会比目前最大的小棒还短。长度最大的原棒的长度不会比所有小棒的长度和还长。这样范围就确定了。
5.我们用深搜用什么参数呢？
首先应该是对某个可能存在的长度（原棒长）进行试探性的验证，看是否能由这所有的小棒组成。那么这个参数是必须的，记为len。
然后，每当“成功”接收一根小木棒（前提是这根小木棒的接收能导致一根完整的木棒被拼出，而不是暂时被接收），那么可用的小木棒数就会相应减1.这个参数很重要（记为num）。
再就是对我们要试探的原木棒可能取值，每当它成功接收一根小木棒，还需要用来拼接一根原木棒的长度就会减小。这也是搜索过程必须知道的量，当它减小到0时，说明一根原木棒拼接完成，它将重新被赋值为len，从而进行下一根木棒的搜索。可知这个参数同样很重要（记为remains)。
6.由于过程中要确定某根小棒是否确定成功被接收，它就得提前预知加入这根小棒后其它的小木棒能不能匹配成功，就叫要求在遍历某个小木棒时，对其后的木棒进行递归搜索（深搜的特点），若能匹配成功，则标记当前小木棒为用过，可以直接返回（试探成功）；若不能匹配，说明此棒目前不可用，将标记取消，待下一次搜索用。若当前木棒不可用，那么与这根小木棒长度相同的木棒也将不可用，直接跳过（剪枝），而且若这个小木棒的长度刚好是reamins_len的长度，那么更能说明后面的不能匹配了，因为如此合适的小棒被接收都不能导至试探成功，后面的小棒更不可能，直接返回0（试探失败 ）（剪枝）。还有就是如果len=remains_len（说明这是新一根原棒，还没有进行匹配），而在预先判断匹配与否时已经判断不能匹配，这样都不能匹配，那么说明以后都不能匹配了（这就是深搜的效果了）。返回0（试探失败）（剪枝）。
7.当remains=0&&num=0说明能用的棒已经没有，而且拼成一根原棒还需的长度为0，只能表示原棒已经完整的由这所有的小棒拼接出来。此时只需返回len（试探成功），这个操作应该放在函数最前。
8.如果深搜完成，仍未返回试探成功，到了函数的最后，只能说明这个试探失败。直接返回0.
9.为了让用过但没有被成功接收的小木棒再次利用，所以函数里对每个小棒进行一次搜索。以让这些漏网的小木棒或许能被再次利用。
10.注意：当换一个原木棒长度进行试探时，要置map为0，否则会与上次搜索混在一起
代码：
#include<iostream> #include<algorithm> #include<cstring> using namespace std; #define N 80 int n; int stick[N]; int map[N]; //用于记录截断后剩下的木棍被使用的情况 bool cmp(int x,int y){ return x>y; } bool dfs(int len,int remain,int num){//len是当前假定的原木棍长，拼成len长的棒还需的长度remain，num是剩下的未拼接的小棒个数 if(remain==0&&num==0) //当还需长度为0且未作接接的小棒个数为0时，说明拼接成功 return true; if(remain==0) //当完成拼接一个棒时，要重新进行下一根木棒拼接，给remain重新赋值 remain=len; for(int i=0;i<n;i++){ if(map[i]) continue; //已经作为成功拼接的小棒，不再作为拼接对象直接跳过 if(stick[i]<=remain){ map[i]=1; //暂时标记为已经用了 if(dfs(len,remain-stick[i],num-1)) //接受这根小棒stick[i]，能完成匹配所有任务，则返回成功拼接棒长 return true; //倘若上述语句执行，则代表处理完stick[i]所有的搭配都是符合的 //因此执行return true返回上一层的这个位置，接着又return true直到dfs结束 map[i]=0; //表示上面搜索不成功，则将标记取消表示未使用状态 //len==remain代表处理一个新的小棒时上述的搜索不成功，则以后搜索均不成功； // stick[i]==remain代表组成len长度现在只需要stick[i]了，但如此合适的小棒都不被接收，后面的小棒更不可能 if(len==remain||stick[i]==remain) break; while(stick[i]==stick[i+1]) i++; //当stick[i]不能完成任务，与它相同长度的小棒也不能完成任务（剪枝） } } return false; } int main(){ while(cin>>n&&n!=0){ int sum=0; memset(stick,0,sizeof(stick)); //清0 for(int i=0;i<n;i++){ cin>>stick[i]; sum+=stick[i]; //sum是截断后木棍的总长 } //先对截断后的木棍排序，从大到小，而sort默认是从小到大，因此加入参数cmp sort(stick,stick+n,cmp); int i=0; for(i=stick[0];i<=sum/2;i++){ memset(map,0,sizeof(map)); if(sum%i==0){ //判断i是否能整除sum（剪枝） if(dfs(i,0,n)){ //搜索成功 cout<<i<<endl; break; } } } if(i>sum/2){ //该原来的木棍不可能位于原长的一半以上且原长以下（剪枝） cout<<sum<<endl; } } return 0; }
以下是具体的剪枝的地方和理解（这里单独给出）：
1.越长的木棍对后面木棍的约束力越大，因此要把小木棍排序，按木棍长度从大到小搜索，这样就能在尽可能靠近根的地方剪枝。（剪枝一）
2.如果当前木棍能恰好填满一根原始木棍，但因剩余的木棍无法组合出合法解而返回，那么让我们考虑接下来的两种策略，一是用更长的木棍来代替当前木棍，显然这样总长度会超过原始木棍的长度，违法。二是用更短的木棍组合来代替这根木棍，他们的总长恰好是当前木棍的长度，但是由于这些替代木棍在后面的搜索中无法得到合法解，当前木棍也不可能替代这些木棍组合出合法解。因为当前木棍的做的事这些替代木棍也能做到。所以，当出现加上某根木棍恰好能填满一根原始木棍，但由在后面的搜索中失败了，就不必考虑其他木棍了，直接退出当前的枚举。（剪枝二）
3.显然最后一根木棍是不必搜索的，因为原始木棍长度是总木棍长度的约数。（算不上剪枝）
4.考虑每根原始木棍的第一根木棍，如果当前枚举的木棍长度无法得出合法解，就不必考虑下一根木棍了，当前木棍一定是作为某根原始木棍的第一根木棍的，现在不行，以后也不可能得出合法解。也就是说每根原始木棍的第一根小木棍一定要成功，否则就返回。（剪枝四）
5.剩下一个通用的剪枝就是跳过重复长度的木棍，当前木棍跟它后面木棍的无法得出合法解，后面跟它一样长度的木棍也不可能得到合法解，因为后面相同长度木棍能做到的，前面这根木棍也能做到。（剪枝五）
说明：
上述代码正确性没有问题，但是过蓝桥杯上的题还是超时（虽然已经减了这么多下枝）
个人思考可能是传入dfs的一些参数不一样，还有些隐藏的剪枝方法在上述代码中体现不了，不过上述代码比较能清晰地展现深搜+优化的思想。
能过蓝桥杯的代码详见：https://www.cnblogs.com/kstranger/p/12240157.html
文章参考来源：
https://blog.csdn.net/cfzjxz/article/details/7433138
https://blog.csdn.net/q573290534/article/details/6623653?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task