题目链接：木棒(AcWing 167)

题目描述

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 50
个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

输入格式

输入包含多组数据，每组数据包括两行。

第一行是一个不超过 64 的整数，表示砍断之后共有多少节木棍。

第二行是截断以后，所得到的各节木棍的长度。

在最后一组数据之后，是一个零。

样例

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

结果

6
5

解题思路

我们可以枚举木棒可能的长度length，然后使用采用dfs判断某个可能的长度是不是答案。按照题意可知木棒长度>=max(所有木棍长度)且<=sum(所有木棍的长度)，此外依照题意还有一个约束条件，就是sum(木棍长度) % length == 0，因为不为0就无法将所有木棍都分好组，如如下代码(sa为木棍总长)：

for length in range(a[0], sa + 1):
        if sa % length != 0: continue
        if dfs(0, 0, 0):#判断该长度是否可以
            print(length)
            break#由于只要最小值因此找到第一个答案就退出

当length固定时可知木棒总共有 sa // length 根(对它们编号，从0开始)
我们在dfs可以枚举哪些木 棍在哪些木 棒当中，即dfs(u, s, start) 中u的含义为当前在枚举编号为u的木 棒可能包含哪些木 棍，s表示已知的包含在u中的木 棍总长， start表示此次应该从编号为start的木 棍开始枚举(这点下方2有解释)，

考虑以下方法对解空间树进行剪枝

1、优化搜索顺序：从大到小枚举（即把木 棍长度降序排序 ）
2、排除等效冗余（比如：u包含编号0，2，3等价于u包含编号3，0，2），为了避免这种“等价”的情况我们应该按照“组合方式”枚举，这就是为什么dfs有一个start参数
3、当枚举到某根木 棍失败了，我们应该不枚举与它相同的木 棍(结果不变，但是可以少搜索很多空间)
4、当我们枚举某个木 棒的第一个木 棍的编号返回False时，直接返回False(原因太长不好讲，见y总视频)，最后一个同理

Python代码

from sys import setrecursionlimit
setrecursionlimit(1000010)
def dfs(u, s, start):
    if u * length == sa: return True#递归出口
    if s == length: return dfs(u + 1, 0, 0)#递归出口
    i = start
    while i <= n - 1:
        if not st[i]:#第i个没用过
            if s + a[i] <= length:#可行性剪纸
                st[i] = True#标记用过
                if(dfs(u, s + a[i], i + 1)): return True
                st[i] = False#回溯

                j = i #采用剪枝方法3
                while j < n and a[i] == a[j]: j += 1
                i = j - 1

                #采用剪枝方法4    
                if s == 0: return False#第一个
                if s + a[i] == length: return False#最后一个
        i += 1
    return False

while True:
    n = int(input())
    if n == 0: break
    a = list(map(int, input().split()))
    a.sort(reverse = True)#优化搜索顺序
    sa = sum(a)
    st = [False] * n#标记某根木棍是不是被用过
    for length in range(a[0], sa + 1):
        if sa % length != 0: continue
        if dfs(0, 0, 0):#判断该长度是否可以
            print(length)
            break#由于只要最小值因此找到第一个答案就退出