木棒

题目

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

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

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

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

输入格式

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

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

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

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

输出格式

为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

数据范围

数据保证每一节木棍的长度均不大于 $50$。

输入样例：

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

输出样例：

6
5

思路

搜索顺序：

1. 从结果入手, 从低到高枚举木棒的最小长度
2. 对于当前长度, 枚举所有木棒
3. 对于当前木棒, 枚举木棍使其组成长度为length的木棒

剪枝优化：

1. 首先肯定存在最大长度, 即把所有木棍都接成一根木棒, 且木棍必须全用上, 说明 sum 是 length 的倍数。
2. 木棒内木棍接的顺序无所谓, 即使用组合方式枚举（定义start）
3. 枚举木棒时从大到小枚举（最小分支优化）
4. 如果当前木棒加上之前的长度大于length, 则continue（可行性剪枝）
5. 当前方案枚举失败时
   1. 若失败时当前木棒长度为0, 即在开头失败, 停止枚举直接回溯 证明：若可以继续枚举, 说明之后存在更小的木棍组合b替代当前木棍a, 又因所有木棒都必须使用, a木棍会放到另一个木棒中任意位置, 而若将a木棍移到左端开始部分, 又说明可以a木棍可以放在开头, 故反证法成立。
   2. 若失败在中间, 即木棒长度不为0也小于length, 可继续枚举
   3. 若失败时当前木棒长度为length, 即s + w[i] == length, 在木棒结尾, 停止枚举直接回溯 证明：若存在更小的木棍组合b（与a长度相同）替代木棍a使其成立, 可以继续枚举, 那么直接用a再替换b, 效果一样。 故用反证法证毕。
   4. 如果在中间且当前失败, 则后面所有相同长度的都可以跳过, 这里从大到小枚举, 故相同长度也相邻, 直接把i往后跳就行。

代码

const int N = 70;
int w[N];
bool st[N];
int sum, length;
int n;
 
bool dfs(int u, int s, int start)
{
    if (u * length == sum)
        return true;
    if (s == length)
        return dfs(u + 1, 0, 0);
 
    for (int i = start; i < n; i++)
    {
        if (st[i])
            continue;
        if (s + w[i] > length)
            continue;
        st[i] = true;
        if (dfs(u, s + w[i], i + 1))
            return true;
        st[i] = false;
 
        // 5-1
        if (!s)
            return false;
 
        // 5-3
        if (s + w[i] == length)
            return false;
 
        // 5-4
        int j = i;
        while (j < n && w[j] == w[i])
            j++;
        i = j - 1;
    }
    return false;
}
 
int main()
{
    while (cin >> n, n)
    {
        sum = 0;
        mem(st, false);
        for (int i = 0; i < n; i++)
        {
            cin >> w[i];
            sum += w[i];
        }
        sort(w, w + n, greater<int>());
        length = 1;
        while (true)
        {
            if (sum % length == 0 && dfs(0, 0, 0))
            {
                cout << length << endl;
                break;
            }
            length++;
        }
    }
    return 0;
}