题目描述

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

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

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

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

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

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

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

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

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

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

输入样例：
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
输出样例：
6
5

算法 DFS + 剪枝 时间复杂度 O(？)

DFS 枚举每组里面应该选哪些物品

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 77;

int w[N],n,sum;

int group,len;

bool st[N];

bool CMP(int a,int b)
{
    return a>b;
}

bool dfs(int u,int cur,int start)
{
    if(u == group) return true;

    if(cur == len) return dfs(u+1,0,0);

    for(int i=start;i<n;i++)
    {
        if(st[i] || cur + w[i]>len) continue;

        st[i] = true;
        if(dfs(u,cur + w[i],i + 1)) return true;
        st[i] = false;

        //剪枝 :
        //如果cur == 0，都无法返回true意味着这个分支中这个组中怎么弄都放不满了
        //如果cur + w[i] == len ,这已经是最理想的情况了，如果这都失败了的话，那这个分支也是失败的
        if(cur == 0 || cur + w[i] == len) return false;

        //剪枝：
        //跳过重复片段，因为选相同长度的物品没有意义
        int j = i;

        while(j<n&&w[i] == w[j]) j++;

        i = j - 1;
    }

    return false;

}

int main(){

    while(~scanf("%d",&n),n)
    {
        memset(st,0,sizeof st);
        sum = 0;
        for(int i=0;i<n;i++)
            scanf("%d",&w[i]) , sum += w[i];

        sort(w,w+n,CMP);//剪枝:按从大到小枚举每一组里面的物品

        len = w[0]; 

        while(true)
        {
            if(sum % len == 0)
            {
                group = sum / len;
                if(dfs(0,0,0))
                    break;
            }
            len ++;

        }

        printf("%d\n",len);

    }


    return 0;
}