DFS(5种剪枝)

没想到Python也能AC! 用时260 ms, 远远小于给C++的时限!

5种剪枝就是教材里面的5种.
自己思考一下, 会发现这5种并不是独立的, 而是有一定的关联的.

在剪枝条件1和剪枝条件2的限制下, 每一根木棒的第一根木棍必须是剩余未使用过的木棍中最长的那根木棍.
如果木棒的第一根木棍失败了, 那意味着这根木棍无处安放了, 如果放在其他的地方, 肯定是与剪枝条件1, 剪枝条件2矛盾的.
因此, 剪枝条件1, 剪枝条件2可以直接推导出剪枝条件4.

Python 代码

# %%
def solve(A):
    def dfs(idx_last, cur, finished):
        """
        输入:
        idx_last: 上一根木棍的序号
        cur: 当前正在拼接木棒的长度
        finished: 已完成的木棒的个数
        输出: bool型, 是否拼接成功
        """
        if finished == S // Len: 
            return True
        # 考虑当前木棒的第一根木棍, 必须是剩余木棍里面最长的那根.        
        if cur == 0:
            for i in range(n):
                if not used[i]:
                    used[i] = True
                    if A[i] == Len:
                        # 第一根木棍就填满了, 直接考虑下一个木棒
                        tf = dfs(i, 0, finished + 1)
                    else:
                        tf = dfs(i, A[i], finished)
                    used[i] = False
                    # 剪枝条件4: 第一根木棍失败, 那么方法肯定失败
                    return tf

        lastA = None
        # 考虑当前木棒的非第一根木棍
        for i in range(idx_last + 1, n):
            if used[i]: continue
            # 剪枝条件3: 若一个木棍失败, 那么等长的其他木棍也肯定会失败
            if A[i] == lastA: continue 
            if cur + A[i] == Len:
                used[i] = True
                tf = dfs(i, 0, finished + 1)
                # 剪枝条件5: 最后一根如果失败, 方案肯定失败
                used[i] = False
                return tf
            elif cur + A[i] < Len:
                used[i] = True
                tf = dfs(i, cur + A[i], finished)
                used[i] = False
                if not tf:
                    lastA = A[i]
                else:
                    return True
        return False


    n = len(A)
    used = [False] * n
    A.sort(reverse=True)
    S = sum(A)
    for Len in range(A[0], S + 1):
        if S % Len: continue
        if dfs(-1, 0, 0):
            return Len


# %%
while True:
    n = int(input())
    if not n: break
    A = list(map(int, input().split()))
    print(solve(A))