poj1011 Sticks（DFS+剪枝）

题目链接

http://poj.org/problem?id=1011

题意

输入n根棍子的长度，将这n根棍子组合成若干根长度相同的棍子，求组合后的棍子的最小长度。这题是poj2362的加强版，思路与poj2362相同，只是在2362的基础上添加了剪枝操作，做这题之前先去做poj2362效果最好。

思路

由于棍子越长，组合时的灵活性越差，所以要先从长棍子开始搜索，则首先要将n根棍子从长到短排序，然后从最长的棍子开始dfs。由于棍子最多可以有64根，不剪枝的话肯定会超时。以下是几种剪枝方法：

（1）假设n根棍子中最长的长度为maxLen，n根棍子的长度和为sum，最后求得的结果为len，则len∈[maxLen，sum]，且sum%len==0;

（2）由于所有的棍子都降序排序，在组合的过程中若某一棍子不合适，则跳过该棍子后面与其长度相同的所有棍子；

（3）最重要的剪枝：在组合新棍子时，如果添加的第一根棍子stick[i]和剩余的所有棍子都无法组合，则不用继续往下搜索，直接返回（如果继续搜索，到最后stick[i]会被剩下）。

代码

未剪枝代码（超时，dfs部分与poj2362的代码基本相同）：

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <vector>
 6 using namespace std;
 7 
 8 const int INF = 1<<30;
 9 const int N = 70;
10 vector<int> stick;
11 int visit[N];
12 int n;
13 int ans;
14 
15 bool cmp(int a, int b)
16 {
17     return a > b;   //棍子从长到短排序
18 }
19 
20 /*
21 * cur : 当前从第cur根棍子开始尝试组合
22 * nums : 当前还有nums根新棍子未组合完成
23 * curLen ：当前组合的棍子长度
24 * len ： 要组合的新棍子长度
25 */
26 bool dfs(int cur, int nums, int curLen, int len)
27 {
28     if(nums==0)
29         return true;
30 
31     for(int i=cur; i<n; i++)
32     {
33         if(visit[i])
34             continue;
35         visit[i] = 1;
36         if(curLen+stick[i]<len)
37         {
38             if(dfs(cur+1, nums, curLen+stick[i], len))
39                 return true;
40         }
41         else if(curLen+stick[i]==len)
42         {
43             if(dfs(0, nums-1, 0, len))
44                 return true;
45         }
46         visit[i] = 0;
47     }
48     return false;
49 }
50 
51 int main()
52 {
53     //freopen("poj1011.txt", "r", stdin);
54     while(cin>>n && n)
55     {
56         int sum = 0;
57         stick.clear();
58         for(int i=0; i<n; i++)
59         {
60             int len;
61             cin>>len;
62             sum += len;
63             stick.push_back(len);
64         }
65 
66         ans = INF;
67         sort(stick.begin(), stick.end(), cmp);
68         for(int i=stick[0]; i<=sum; i++)
69         {
70             if(sum % i != 0)    
71                 continue;
72             memset(visit, 0, sizeof(visit));
73             if(dfs(0, sum/i, 0, i))
74             {
75                 cout<<i<<endl;
76                 break;
77             }
78         }
79     }
80     return 0;
81 }

剪枝后代码（AC）：

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int INF = 1<<30;
const int N = 70;
vector<int> stick;
int visit[N];
int n;
int ans;

bool cmp(int a, int b)
{
    return a > b;   //棍子从长到短排序
}

/* 
* cur : 当前从第cur根棍子开始尝试组合
* nums : 当前还有nums根新棍子未组合完成
* curLen ：当前组合的棍子长度
* len ： 要组合的新棍子长度
*/
bool dfs(int cur, int nums, int curLen, int len)
{
    if(nums==0)
        return true;

    int same = -1;  //剪枝（2）
    for(int i=cur; i<n; i++)
    {
        if(visit[i] || stick[i]==same)
            continue;
        visit[i] = 1;
        if(curLen+stick[i]<len)
        {
            if(dfs(cur+1, nums, curLen+stick[i], len))
                return true;
            else same = stick[i];
        }
        else if(curLen+stick[i]==len)
        {
            if(dfs(0, nums-1, 0, len))
                return true;
            else same = stick[i];
        }
        visit[i] = 0;
        if(curLen==0)   //剪枝（3）
            break;
    }
    return false;
}

int main()
{
    //freopen("poj1011.txt", "r", stdin);
    while(cin>>n && n)
    {
        int sum = 0;
        stick.clear();
        for(int i=0; i<n; i++)
        {
            int len;
            cin>>len;
            sum += len;
            stick.push_back(len);
        }

        ans = INF;
        sort(stick.begin(), stick.end(), cmp);
        for(int i=stick[0]; i<=sum; i++) 
        {
            if(sum % i != 0)    //剪枝（1）
                continue;
            memset(visit, 0, sizeof(visit));
            if(dfs(0, sum/i, 0, i))
            {
                cout<<i<<endl;
                break;
            }
        }
    }
    return 0;
}