> #include <iostream>
> #include <fstream>
> 
> using namespace std;
> #define MAX 64
> #define VERYLARGE 1000000
> 
> int stick[MAX];
> int diff[MAX];      //  在第几中被占用了
> int mark[MAX];      //  在第几中被占用了
> int nCount, nSum, nResult = 0;
> 
> int IsFinished(int nMark)
> {
>     for (int i = 0; i < nCount; i ++)
>     {
>         if (mark[i] > nMark) return 0;
>     }
>     return 1;
> }
> 
> void dfs(int nGoal, int nTemp, int nBegin, int nMark) // 计算函数
> {       // 从stick中由nBegin开始找出小于 nGoal - nTemp的数
>         // 现在已经的和为nTemp,nMark该组起始数的索引为（用以区分）
>     // 全搜索、遍历所有可能
>     int i;
>     for (i = nBegin; i < nCount; i ++)  
>     {
>         if (!(mark[i] > nMark && !nResult && nTemp + stick[i] <= nGoal))
>             continue;
>         mark[i] = nMark;
>         if (stick[i] + nTemp == nGoal)   // 如果相等
>         {
>             if (IsFinished(nMark)) 
>             {
>                 nResult = nGoal;  return;
>             }//
>             dfs(nGoal, 0, nMark + 1, nMark + 1);
>         }
>         else
>         {
>             dfs(nGoal, nTemp + stick[i], i + 1, nMark);
>         }
>         if (!nResult)
>             mark[i] = VERYLARGE;
>         while (!nResult && i < nCount && stick[i] == stick[i + 1]) i ++; // 剪枝
>     }   // for
> }
> 
> int calculate()
> {
>     int i;
>     for (i = stick[0]; i < nSum; i ++)
>     {
>         if (nResult) break;
>         if (!(nSum % i)) dfs(i, 0, 0, 0);
>     }
>     if (!nResult)
>         nResult = nSum;
>     return nResult;
> }
> 
> int compare(const void* a,const void* b)
> {
>     return *(int*)b - *(int*)a ;
> }
> 
> int main()
> {
>     cin >> nCount;
>     while (nCount)
>     {
>         if (nCount < 0 || nCount > 64) 
>             continue;
>         memset((void*)stick, 0, sizeof(int) * MAX); //清零
>         int i;
>         nSum = 0;
>         for (i = 0; i < nCount; i ++)
>         {
>             cin >> stick[i];
>             if(stick[i] > 50 || stick[i] <= 0)
>                 stick[i] = 0;
>             mark[i] = VERYLARGE;
>             nSum += stick[i];
>         }   //  for
> 
>         nResult = 0;
>         //  开始计算
>         qsort(stick, nCount, sizeof(int), compare);
>         int j = 0;
>         for (i = 0; i < nCount - 1; i ++)
>         {
>             diff[i] = 0;
>             if (stick[i] != stick[i + 1])
>                 diff[i] = i + 1;
>         }
>         
>         calculate();
>         cout << nResult << endl;
>         cin >> nCount;
>     };  //  while
> 
>     return 0;
> }

• Re:记得按LRJ黑书上的说法，如果搜索顺序和剪枝OK的话，满足题意的任何数据运算都不会超过100ms (23) piratelzs 2006-12-30 15:11:35