学步园

题意：给n（n<=64）根小木棒，每根木棒长度最大为50，问最小能把他们拼成长度为多少的木棒使得小木棒不剩余。

题解：经典dfs+剪枝。总结起来三个剪枝，具体见代码。

Sure原创，转载请注明出处

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
const int maxn = 70;
int stick[maxn];
bool vis[maxn];
int sum,n,cur;

bool cmp(const int &a,const int &b)
{
    return a > b;
}

void read()
{
    sum = 0;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&stick[i]);
        sum += stick[i];
    }
    sort(stick , stick + n , cmp);
    return;
}

bool dfs(int st,int cnt,int len)
{
    if(len == cur)   //剪枝1 : 对于当前长度为cur的第一根木棒一定是剩余最大的
    {
        for(int i=0;i<n;i++)
        {
            if(vis[i] == false)
            {
                vis[i] = true;
                if(dfs(i+1,cnt,len-stick[i]) == false)
                {
                    vis[i] = false;
                    return false;
                }
                return true;
            }
        }
        return false;
    }
    if(len == 0)
    {
        if(cnt == 1) return true;
        else return dfs(0,cnt-1,cur);
    }
    for(int i=st;i<n;i++)
    {
        if(vis[i]) continue;
        if(i > 0 && vis[i-1] == false && stick[i] == stick[i-1]) continue;  //剪枝2 : 如果i小木棒和i-1小木棒长度相等且i-1未使用，则跳过i
        if(len >= stick[i])
        {
            vis[i] = true;
            if(dfs(i+1 , cnt , len - stick[i])) return true;
            vis[i] = false;
            if(len == stick[i]) return false;  //剪枝3 : 如果当前最后一根木棒恰好为剩余长度都不能满足，那么直接返回上一层
        }
    }
    return false;
}

void solve()
{
    int res = -1;
    for(int i=stick[0];i<sum;i++)
    {
        if(sum % i == 0)
        {
            memset(vis,false,sizeof(vis));
            cur = i;
            if(dfs(0,sum/i,i))
            {
                res = i;
                break;
            }
        }
    }
    if(res == -1) res = sum;
    printf("%d\n",res);
    return;
}

int main()
{
    while(scanf("%d",&n) && n)
    {
        read();
        solve();
    }
    return 0;
}