DFS+剪枝（经典木棍问题）

目录

• DFS+剪枝（经典木棍问题）

题目

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序，帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
输入格式
输入包含多组数据，每组数据包括两行。
第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。
第二行是截断以后，所得到的各节木棍的长度。
在最后一组数据之后，是一个零。
输出格式
为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。
数据范围
数据保证每一节木棍的长度均不大于50。

分析

最重要：剪枝操作

1. 优化搜索顺序（尽量选择决策少的点进行扩展）：按木棍长度从大到小排序 ->（类似于见缝插针，缝越大越难插）
   具体操作：枚举所有木棍长度，每次枚举时判断长度是否可行，找到第一个满足要求的长度就返回。显然，所有木棍长度的总和要能整除每根木棍长度。按照木棍顺序来拼接。
2. 木棍内部编号递增
   解释：防止出现重复。长度为x在前,y在后的木棍与y在前,x在后的木棍是一样的。
3. 跳过所有相等的木棍
   解释：假设要拼的下一根编号为i的木棍拼接失败，那么如果第i+1根木棍长度与第i根木棍相等，则一定失败，因此可以跳过之后所有相等的木棍。
4. 如果放第一个或最后一个木棒失败了，则分治失败
   解释：如果某根木棍是加入的第一根，而且失败了，那么就不用循环后面的木棍作为当前要拼的木棒的第一根了，也一定会失败。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 64;
int n, sum, length;//sum表示所有木棒总和
int sticks[N];
bool st[N]; //记录木棒是否被用过

bool cmp(int a,int b) //剪枝一：木棍长度从大到小排序
{
    return a>b;
}

bool dfs(int u, int cur, int stk)
{
    if(u * length == sum) return true; //拼好的木棍个数乘上长度等于总和，结束
    if(cur == length) return dfs(u+1, 0, 0);  //当前木棒长度等于目标长度，枚举下一根木棒
    for(int i=stk; i<n; i++)             //剪枝二：木棍内部编号递增
    {
        if(st[i]) continue;
        int l = sticks[i];
        if(l + cur > length) continue;
        st[i] = true;
        if(dfs(u, cur+l, i+1)) return true;
        st[i] = false;                 //恢复现场
        //剪枝四：如果放第一个或最后一个木棒失败了，则分治失败
        if(!cur) return false;
        if(cur + l == length) return false;
        //剪枝三：跳过所有相等的木棍
        int j = i;                              
        while(j < n && sticks[j]==l) j++;
        i = j-1;    
    }
    return false;
}

int main()
{
    while(cin >> n, n)
    {
        sum = 0, length = 0;
        for(int i=0; i<n; i++)
        {
            int l;
            cin >> l;
            sticks[i] = l;         //当前木棒长度为l
            if(l > 50) continue;
            sum += l;              //更新sum 和 length
            length = max(length, l);
        }
        sort(sticks, sticks+n, cmp);
        memset(st, false, sizeof st);
        for(int i=0; i<n; i++)
            if(sticks[i] > 50)
                st[i] = true;
        while(length)             //从小到大枚举所有length
        {
            if(sum%length==0 && dfs(0, 0, 0))
            //第一个0表示从第一根木棒开始，第二个0表示当前枚举的木棍已经拼好多长，第三个0表示当前木棒起始下标
            {
                cout << length << endl;
                break;
            }
            length++;
        }
    }
    return 0;
}

​

​