学步园

转载来源:

http://blog.csdn.net/lyy289065406/article/details/6661449

这道题比较特殊,用DFS也是对的,而且可以进行优化,即使直接n[i]--也是对的.解释见注释.

//Memory Time
    //440K 16MS

    /*DFS*/

    #include<iostream>
    using namespace std;

    int n[7];  //价值为i的物品的个数
    int SumValue;  //物品总价值
    int HalfValue;  //物品平分价值
    bool flag;    //标记是否能平分SumValue

    void DFS(int value,int pre)
    {
        if(flag)
            return;

        if(value==HalfValue)
        {
            flag=true;
            return;
        }
//为什么可以n[i]--而不回溯呢？
//因为只要从剩下的物品中选出一半，那么尝试失败的那些选择都可以认为是给了对方。
//因为从分叉点之下，失败的代价总是在剩下的half之内.
//如果回溯的话就会TLE了
        for(int i=pre;i>=1;i--)
        {
            if(n[i])
            {
                if(value+i<=HalfValue)
                {
                    n[i]--;
                    DFS(value+i,i);

                    if(flag)
                        break;
                }
            }
        }
        return;
    }

    int main()
    {
        int test=1;
        while(cin>>n[1]>>n[2]>>n[3]>>n[4]>>n[5]>>n[6])
        {
            SumValue=0;  //物品总价值

            for(int i=1;i<=6;i++)
                SumValue+=i*n[i];

            if(SumValue==0)
                break;

            if(SumValue%2)    //sum为奇数，无法平分
            {
                cout<<"Collection #"<<test++<<':'<<endl;
                cout<<"Can't be divided."<<endl<<endl;    //注意有空行
                continue;
            }

            HalfValue=SumValue/2;
            flag=false;

            DFS(0,6);

            if(flag)
            {
                cout<<"Collection #"<<test++<<':'<<endl;
                cout<<"Can be divided."<<endl<<endl;
                continue;
            }
            else
            {
                cout<<"Collection #"<<test++<<':'<<endl;
                cout<<"Can't be divided."<<endl<<endl;
                continue;
            }
        }
        return 0;
    }

分析不清楚的时候1可借助小规模实例,2可借助debug单步

下面是更通用的DP解法~

//Memory Time   
//644K  0MS   
  
/*多重背包+二进制优化*/  
  
#include<iostream>  
using namespace std;  
  
int n[7];  //价值为i的物品的个数  
int v;  //背包容量  
int SumValue;  //物品总价值  
bool flag;    //标记是否能平分SumValue  
int dp[100000];  //状态数组  
  
int max(int a,int b)  
{  
    return a>b?a:b;  
}  
  
/*完全背包*/  
void CompletePack(int cost,int weight)  
{  
    for(int i=cost;i<=v;i++)  
    {  
        dp[i]=max(dp[i],dp[i-cost]+weight);  
        if(dp[i]==v)    //剪枝，当能够平分SumValue时退出  
        {  
            flag=true;  
            return;  
        }  
    }  
              
    return;  
}  
  
/*01背包*/  
void ZeroOnePack(int cost,int weight)  
{  
    for(int i=v;i>=cost;i--)  
    {  
        dp[i]=max(dp[i],dp[i-cost]+weight);  
        if(dp[i]==v)    //剪枝  
        {  
            flag=true;  
            return;  
        }  
    }  
    return;  
}  
  
/*多重背包*/  
void MultiplePack(int cost,int weight,int amount)  
{  
    if(cost*amount>=v)  
    {  
        CompletePack(cost,weight);  
        return;  
    }  
  
    if(flag)    //剪枝  
        return;  
  
    /*二进制优化*/  
    int k=1;  
    while(k<=amount)  
    {  
        ZeroOnePack(k*cost,k*weight);  
  
        if(flag)    //剪枝  
            return;  
  
        amount-=k;  
        k*=2;  
    }  
    ZeroOnePack(amount*cost,amount*weight);  
  
    return;  
}  
  
int main()  
{  
    int i,test=1;  
    while(cin>>n[1]>>n[2]>>n[3]>>n[4]>>n[5]>>n[6])  
    {  
        SumValue=0;  //物品总价值  
  
        for(i=1;i<=6;i++)  
            SumValue+=i*n[i];  
  
        if(SumValue==0)  
            break;  
  
        if(SumValue%2)    //sum为奇数，无法平分  
        {  
            cout<<"Collection #"<<test++<<':'<<endl;  
            cout<<"Can't be divided."<<endl<<endl;    //注意有空行  
            continue;  
        }  
  
        v=SumValue/2;  
        memset(dp,-1,sizeof(dp));  
        dp[0]=0;  
        flag=false;  
  
        for(i=1;i<=6;i++)  
        {  
            MultiplePack(i,i,n[i]);  
  
            if(flag)    //剪枝  
                break;  
        }  
  
        if(flag)  
        {  
            cout<<"Collection #"<<test++<<':'<<endl;  
            cout<<"Can be divided."<<endl<<endl;  
            continue;  
        }  
        else  
        {  
            cout<<"Collection #"<<test++<<':'<<endl;  
            cout<<"Can't be divided."<<endl<<endl;  
            continue;  
        }  
    }  
    return 0;  
}