poj1014Dividing

发表于: 2013年02月09 00:00

题目大意如下:有6种物品,都有不同的价值(分别为1,2,3,4,5,6)和数量. 问是否可以将他们分成两个相等的部分.

思路: 很暴力的险过.dp[i]表示,物品价值为i的情况是否出现. 那么我们枚举每一种物品.和价值.如果出现总价值的的一半.则可以平分.

:::c++
//bnu1133
#include<stdio.h>
#include<string.h>
bool dp[60001];
int ss[7];
//用dp险过
bool mydp(int sum)
{
    int max=0;
    memset(dp,0,sizeof(dp));
    if(sum%2==0)//简单减枝
    {
        sum/=2;
        dp[0]=true;//一人拥有所有物品,另一个人什么也没有的情况
        for(int j=1;j<=6;j++)
        {
            if(ss[j]>0)
            {
                for(int i=max;i>=0;i--)//价值从大到小进行枚举
                {
                    if(dp[i])//如果价值为i的情况出现过.
                    {
                        for(int k=1;k<=ss[j];k++)//
                        {
                            int a=i+k*j;
                            if(sum==a) return true;
                            else if(a<sum && !dp[a])
                            {
                                dp[a]=true;
                                max=a>max?a:max;
                            }
                            else if(a>sum)
                                max=sum;
                        }
                    }
                }//for
            }//if
        }//for
    }
    return false;
}
int main()
{
    int n,i,sum;
    int ca=0;
    while(1)
    {
        sum=0;
        ca++;
        for(i=1;i<=6;i++)
        {
            scanf("%d",&ss[i]);
            sum+=ss[i]*i;
        }
        if(sum==0) break;
        printf("Collection #%d:\n",ca);
        if(mydp(sum))
            printf("Can be divided.\n");
        else
            printf("Can't be divided.\n");
        putchar('\n');
    }
}
© 2018 - fluyy - 粤ICP备17114935号