来源

ACwing167-木棒

POJ1011-Sticks

题目简介

本题被称为是剪枝神题之一，因为剪枝角度多达5种，且难以想象。常规的深搜，普通剪枝无法完成此题很有可能会导致超时。

笔者解析

剪枝五种方法列举

  1. 从大到小排列数组（我们优先使用较长的短木棒，这样可以避免出现类似10=2+3+5，及明明可以用一根却用了三根短木棒的情况）
  2. 木棒内部编号递增，帮助递归下标管理
  3. 在爆搜过程中，如果任意大木棒的第一个短木棍在进行了DFS爆搜后，显示这个短木棒不能匹配成指定长度len，但每条短木棍是一定要用的，所以只能说明这个len不满足题意，返回false
  4. 在爆搜过程中，如果任意大木棒的加了最后一块需要的短木棒在进行了DFS爆搜后，虽然当前小木棒加上后可以匹配一个完整的大木棒，但显示不能匹配，说明在接下来的爆搜过程中有则后面至少有一根大木棍不能用短木棒匹配成len，所以当前len依旧不满足题意，返回false
  5. 不能匹配后，则跳过所以相等的木棍长度，因为一样的长度同样通不过匹配

笔者代码

java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n,sum = 0,len;
    static int[] arr,visit;
    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        while (true){
            //输入木棍个数，当n为0时结束
            n = scanner.nextInt();
            if(n == 0){break;}
            arr = new int[n];
            visit = new int[n];
            int m;
            for (int i = 0; i < n; i++) {
                m = scanner.nextInt();
                //长度不大于50if(m>50){continue;}
                arr[i] = m;
                //计算总和
                sum+=arr[i];
            }

            //递增排列短木棍
            Arrays.sort(arr);
            //二分递减排列短木棍
            int l = 0,r=n-1;
            while(l<r){
                arr[l] = arr[l]+arr[r];
                arr[r] = arr[l] - arr[r];
                arr[l] = arr[l] - arr[r];
                l++;
                r--;
            }

            //逐个排列可能性,从最长的木棍长度开始
            for (len = arr[0];len <= sum/2; len++) {
                //当sum/len为整数时，说明有可能被拼凑出来,使用DFS判定
                if(sum%len == 0&&DFS(0,0,0)==true){
                    System.out.println(len);
                    break;
                }
            }

            if(len>sum/2){
                //只有一根木棍的情况下，最小长度为sum
                System.out.println(sum);
            }
            
            sum = 0;
        }
    }

    static boolean DFS(int lon,int index,int num){//分别表示：当前木大棒长度，当前短木棒下标，当前大木棒个数

        //当大木棒个数乘当前目测长度等于总长时，返回ture
        if(num * len == sum){return true;}

        //当当前木棒长度为预测大棒长度时，说明已经找到一个木棒了,DFS寻找下一个木棒
        if(lon == len){return DFS(0,0,num+1);}

        for (int i = index; i < n; i++) {
            //若当前的小木棍已经被用过,或当遍历的小木棍加上当前的木棍长度后大于len，则跳过继续
            if(visit[i] == 0&&lon+arr[i]<=len){

                visit[i] = 1;
                if(DFS(lon+arr[i],i+1,num)){return true;}
                visit[i] = 0;

                //如果当前是要放入的第一根短木棒，就放入出错出现问题，则此len无法满足条件，返回false
                //说明在前面一轮的DFS中，没有短木棒能和这个初始短木棒组成长度为len的大木棒，但这个木棒是不能跳过的,我迟早要用这个长度的短木棒组成木棒的
                //因为就算跳过，在后面也要使用他和其它木棒组合，所以认定这个len不能被满足
                if(lon == 0){return false;}

                //如果是放入最后一节短木棒就放入出错，则此len无法满足条件，返回false
                //当发现前面的DFS并没有让lon+arr[i]=len这一看似可以通过的数据通过
                // 说明当前这一根大木棒虽然能凑成，但后面总有一根木棒他凑不出来
                if(lon+arr[i] == len){return false;}

                //跳过所有相等的木棍,因为当前的木棒已经失败了，相同的长度同样会失败
                int j = i+1;
                while (j< n && arr[i] == arr[j]){j++;}
                i = j-1;
            }
        }
        //若到了最后一个要拼凑的小木棍无法找到，则这种方法不合法
        return false;
    }
}

c++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 70;
int w[N];
int len,n,sum;
bool st[N];

bool dfs(int u,int s,int start)//u表示多少个大木棒，s表示当前大木棒的长度,start表示木棒的下标
{
    if(u * len == sum) //当前大木棒个数乘大木棒长度等于所有木棒总和，代表已经找到答案了，返回true
        return true;
    
    if(s == len) //已经找到一个小木棒了，小木棒个数加1，递归搜索下一个小木棒
        return dfs(u + 1, 0 ,0);
    
    for(int i = start; i < n; i ++ )//答案是个组合数，不是排列数
    {
        if(!st[i] && s + w[i] <= len)//可行性剪枝，当前木棒之前没被用过，或者当前大木棒总长度加上小木棒长度小于等于len
        {
            st[i] = true;
            if(dfs(u, s + w[i], i + 1))//判断当前木棒是否能放下
                return true;//当前木棒能放到当前位置
            st[i] = false;
            
            //如果程序运行到这，代表当前小木棒不能放到这个位置
            if(s == 0) //代表当前木棒为大木棒的第一个失败
                return false;
            if(s + w[i] == len)//放到最后一个位置也失败了
                return false;
            int j = i + 1;//如果i失败了,那么长度跟i一样的棍子也一定失败
            while(j < n && w[i] == w[j]) j++;
            i = j - 1;
        }
    }
    return false;//枚举完了还没有成功,就返回失败
}

int main()
{
    while(cin>>n)
    {
        if(n==0) break;
        sum = 0;
        for (int i = 0; i < n; i ++ )
        {
            cin>>w[i];
            sum+=w[i];
        }
        
        sort(w,w+n);
        reverse(w,w+n);//从大到小排序，优化搜索顺序
        
        len = w[0];//从最大的那个木棒开始，因为不可能有一个大木棒比一个小木棒还小
        bool flag = true;
        while(len<=sum/2)
        {
            if(sum % len != 0)//可行性剪枝，答案肯定是总和的约数
            {
                len++;
                continue;
            }
            if(dfs(0,0,0))
            {
                memset(st, false, sizeof st);
                cout << len <<endl;
                flag = false;
                break;
            }
            len++;
        }
        if(flag)//还没找到答案，所以答案只能是所有木棒长度总和
            cout << sum <<endl;
    }
    return 0;
}