神奇的剪枝操作



poj1011 各种神奇的剪枝操作

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

int a[65], sum, n, num, length;
bool available[65], flag = false;

bool cmp(int x, int y)
{
    return (x > y);
}

void dfs(int i, int now_sum, int num)
{
    if(num == 1)//剩1根即可跳出循环
    {
        printf("%d\n", length);
        flag = true;
        return;
    }
    if(now_sum == length)
    {
        /*
        for(int j = 0; j < n; j++)//for testing
        {
            if(!available[j]) cout << j << ' ';
        }
        cout << endl;
        */
        //putchar('\n');
        /*
        *当要拼一根新的木棍的时候，
        *如果这跟最长的木棍也拼不出来，再短的木棍也不能做到拼成新的
        *（迟早会用上最长的）
        *这样能剪去很多对较小的数的反复搜索
        */
        for(i = 0; i < n && !available[i]; ++i);
        available[i] = false;
        dfs(i + 1, a[i], num - 1);
        available[i] = true;
        if(available[i]) return;
    }
    for(; i < n; ++i)
    {
        if(available[i] && (now_sum + a[i] <= length))
        {
            available[i] = false;
            //printf("choose %d\n", i);
            dfs(i + 1, now_sum + a[i], num);
            if(flag) return;//已经找到解
            available[i] = true;
            for(;a[i] == a[i + 1]; ++i);//去重剪枝，相同木棍没区别。
        }
    }
}

int main()
{
    //freopen("1011.txt", "r", stdin);
    scanf("%d", &n);
    while(n != 0)
    {
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        sort(a, a + n, cmp);
        for(length = a[0]; (length <= sum / 2); ++length)
        {
            if(sum % length == 0)
            {
                memset(available, 1, sizeof(available));
                //printf("dfs:%d\n", length);
                num = sum / length;
                dfs(0, length, num + 1);
                if(flag) break;
            }
        }
        if(!flag) printf("%d\n", sum);

        scanf("%d", &n);
        sum = 0;
        flag = false;
    }
    //fclose(stdin);
}