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的代码基本相同）：

 #include <algorithm>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <vector>

 using namespace std;

 const int INF = <<;

 const int N = ;

 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==)

         return true;

     for(int i=cur; i<n; i++)

     {

         if(visit[i])

             continue;

         visit[i] = ;

         if(curLen+stick[i]<len)

         {

             if(dfs(cur+, nums, curLen+stick[i], len))

                 return true;

         }

         else if(curLen+stick[i]==len)

         {

             if(dfs(, nums-, , len))

                 return true;

         }

         visit[i] = ;

     }

     return false;

 }

 int main()

 {

     //freopen("poj1011.txt", "r", stdin);

     while(cin>>n && n)

     {

         int sum = ;

         stick.clear();

         for(int i=; 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[]; i<=sum; i++)

         {

             if(sum % i != )

                 continue;

             memset(visit, , sizeof(visit));

             if(dfs(, sum/i, , i))

             {

                 cout<<i<<endl;

                 break;

             }

         }

     }

     return ;

 }

剪枝后代码（AC）：

#include <algorithm>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

const int INF = <<;

const int N = ;

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==)

        return true;

    int same = -;  //剪枝（2）

    for(int i=cur; i<n; i++)

    {

        if(visit[i] || stick[i]==same)

            continue;

        visit[i] = ;

        if(curLen+stick[i]<len)

        {

            if(dfs(cur+, nums, curLen+stick[i], len))

                return true;

            else same = stick[i];

        }

        else if(curLen+stick[i]==len)

        {

            if(dfs(, nums-, , len))

                return true;

            else same = stick[i];

        }

        visit[i] = ;

        if(curLen==)   //剪枝（3）

            break;

    }

    return false;

}

int main()

{

    //freopen("poj1011.txt", "r", stdin);

    while(cin>>n && n)

    {

        int sum = ;

        stick.clear();

        for(int i=; 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[]; i<=sum; i++)

        {

            if(sum % i != )    //剪枝（1）

                continue;

            memset(visit, , sizeof(visit));

            if(dfs(, sum/i, , i))

            {

                cout<<i<<endl;

                break;

            }

        }

    }

    return ;

}