tanxing.txt

经典的剪枝

PKU1011，一个经典贪心搜索＋剪枝。
题目大意：n根小棍，拼成若干根长棍，要这些长棍的长度相等，并且小棍刚好都用完，问能拼成的长棍的最短长度是多少。
思路：
         首先把小棍按长度，从大到小排序(为了进行贪心选择)，并计算这些小棍的总长度，拼成的长棍的长度从最长的小棍开始搜索，如果小棍的总长度能整除该长棍长度，则可能完成拼凑，问题简化成n根小棍，长度已知，拼成num_stick根长度为l的长棍，能否完成，若能，输出l，结束；否则，增加长棍的长度，继续搜索，最坏的情况下，所有的小木棍一起，能拼成一根长木棍，所以，搜索终能成功。
程序的main函数完成这部分功能。
        现在在问题是，如何判断n根小棍，能够拼成长度为l的num_stick根长棍。solve函数解决这个问题。每次凑长棍的过程，可以看成是从未使用的小棍(长度大到小排序)中进行尝试，贪心原则是，如果有比较长的小棍能满足条件，一定先选上。一次凑长棍的过程：第1根小棍，从0..n-1(未用部分)中尝试，第2根小棍则只需要从1..n-1中尝试，因为第0根小棍要么以前凑长棍的时候就被用了，否则在选第一根小棍的时候一定选上了，这样，第i根小棍只要在第i-1..n-1中进行尝试即可。
剪枝：1。每次凑长棍的第一次选择时，一定成功选取可选的最长的小棍；
             2。在凑某根长棍过程中，选第i根小棍时，要在第i-1..n-1根小棍中尝试，如果尝试了第k根小棍，后面与第k根小棍等长的小棍就不必再尝试。
        本题暴力搜索或剪枝不当，一定TLE。
代码如下：
＃i nclude <stdio.h>
＃i nclude <algorithm>
using namespace std;
const int N = 64;
int a[N]; //小木棍长度 
int n; //小木棍数目
int l; //凑成木棍的长度
int num_stick; //凑成木棍的数目 
int used[N]; //小木棍是否被使用
int ok; //是否成功
 
int cmp(int a,int b)
{
  return a>b;
}

//k 从第k个小棍开始搜
//sum 积累的棍子长度
//cnt 搜第cnt根棍子 
void solve(int k,int sum,int cnt)
{
  if(cnt > num_stick)
  {
    ok = 1;
    return;
  }
  if(sum == l)
  {
    solve(0,0,cnt+1);
  }
  else
  {
    int old = -1; //前一次的选择 
    for(int i = k;i<n;i++)
    if(used[i] == 0)
    {
      //剪枝：和上一次的一样，不必尝试！ 
      if(a[i] == old)
        continue;
      //剪枝：第一次选，肯定选最长的！ 
      if(sum == 0)
      {
         used[i] = 1;
         old = a[i];
         solve(i+1,sum+a[i],cnt);
         used[i] = 0;
         return;
      }
      if(a[i]+sum<=l)
      {
         used[i] = 1;
         old = a[i];
         solve(i+1,sum+a[i],cnt);
         used[i] = 0;
         if(ok)
            return;
      }
    }
  } 
  
} 
int main()
{
   while(scanf("%d",&n) && n!=0)
   {
      int i;
      int total = 0;
      for(i = 0;i<n;i++)
      {
         scanf("%d",&a[i]);
         total += a[i];
      }
      sort(a,a+n,cmp);
      for(i = a[0];i<=total;i++)
       if(total%i == 0)
      {
        l = i;
        num_stick = total/i;
        memset(used,0,N*sizeof(int));
        ok = 0;
        solve(0,0,1);
        if(ok)
        {
          printf("%d\n",i);
          break;
        } 
      }
   }  
}