首页 > 代码库 > [POJ 1011]Sticks(DFS剪枝)

[POJ 1011]Sticks(DFS剪枝)

2024-07-18 18:56:28   217人阅读

Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

Input

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

Output

The output should contains the smallest possible length of original sticks, one per line.

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6
5

Source

Central Europe 1995

此题一共有4种剪枝方案：

1、之前的一根棍子安装失败，之后不尝试所有与其长度相同的棍子

2、若正在替换一整根棍子中的第一根棍子，则返回失败（替换每个整根棍子中的第一根无法扭转失败局面）

3、保证安装上去的棍子顺序为从长到短，之后每次尝试新棍子，只会选择比最近安装上去的棍子更小的棍子

4、若正在替换一整根棍子中的最后一根棍子，则返回失败（替换每个整根棍子中的最后一根无法扭转失败局面）

（一）只采取了1、2剪枝方案的代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define MAXN 1000
#define cls(array,num) memset(array,num,sizeof(array))

using namespace std;

int n,stick[MAXN],L;
bool bUsed[MAXN]; //标记木棒是否被用过

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

bool DFS(int R,int M) //还有R根木棒，剩余长度为M
{
    if(R==0&&M==0) return true; //任务完成
    if(M==0) M=L; //一根棍子拼完，开始拼新的一根
    for(int i=1;i<=n;i++)
    {
        if(!bUsed[i-1]&&stick[i]==stick[i-1]) continue; //剪枝1。之前一根木棒与这根木棒长度相同，但之前那根木棒装不上去，跳过
        if(bUsed[i]) continue;
        if(stick[i]<=M)
        {
            bUsed[i]=true;
            if(DFS(R-1,M-stick[i])) return true;
            else
            {
                bUsed[i]=false;
                if(M==L) return false; //剪枝2。在换第一根棍子，这是徒劳的，无论把第一根棍子换成其他任何棍子都将失败，返回false
            }
        }
    }
    return false;
}

int main()
{
    while(1)
    {
        cls(stick,0);
        int nTotalLen=0;
        cin>>n;
        if(!n) return 0;
        for(int i=1;i<=n;i++)
        {
            cin>>stick[i];
            nTotalLen+=stick[i];
        }
        sort(stick+1,stick+n+1,cmp);
        for(L=stick[n];L<=nTotalLen/2;L++) //L是每个拼好的棍子长度
        {
            cls(bUsed,0);
            if(nTotalLen%L) continue; //L不能整除总长度，显然不行，跳过
            if(DFS(n,L))
            {
                cout<<L<<endl;
                break;
            }
        }
        if(L>nTotalLen/2) cout<<nTotalLen<<endl; //如果之前所有长度都不可取，则说明处理后只能拼成一整根棍子
    }
    return 0;
}
（二）采用了4种剪枝方案强剪枝的代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define MAXN 1000
#define cls(array,num) memset(array,num,sizeof(array))

using namespace std;

int n,stick[MAXN],L;
bool bUsed[MAXN]; //标记木棒是否被用过

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

bool DFS(int R,int M) //还有R根木棒，剩余长度为M
{
    if(R==0&&M==0) return true; //任务完成
    if(M==0) M=L; //一根棍子拼完，开始拼新的一根
    for(int i=1;i<=n;i++)
    {
        if(!bUsed[i-1]&&stick[i]==stick[i-1]) continue; //剪枝1。之前一根木棒与这根木棒长度相同，但之前那根木棒装不上去，跳过
        if(bUsed[i]) continue;
        if(stick[i]<=M)
        {
            bUsed[i]=true;
            if(DFS(R-1,M-stick[i])) return true;
            else
            {
                bUsed[i]=false;
                if(M==L) return false; //剪枝2。在换第一根棍子，这是徒劳的，无论把第一根棍子换成其他任何棍子都将失败，返回false
            }
        }
    }
    return false;
}

int main()
{
    while(1)
    {
        cls(stick,0);
        int nTotalLen=0;
        cin>>n;
        if(!n) return 0;
        for(int i=1;i<=n;i++)
        {
            cin>>stick[i];
            nTotalLen+=stick[i];
        }
        sort(stick+1,stick+n+1,cmp);
        for(L=stick[n];L<=nTotalLen/2;L++) //L是每个拼好的棍子长度
        {
            cls(bUsed,0);
            if(nTotalLen%L) continue; //L不能整除总长度，显然不行，跳过
            if(DFS(n,L))
            {
                cout<<L<<endl;
                break;
            }
        }
        if(L>nTotalLen/2) cout<<nTotalLen<<endl; //如果之前所有长度都不可取，则说明处理后只能拼成一整根棍子
    }
    return 0;
}
两种代码速度差异实在太大，令人惊讶！




联系
我们