设为首页 加入收藏

TOP

多重背包+二进制优化(三)
2012-11-10 11:52:07 来源: 作者: 【 】 浏览:810
Tags:多重 背包 二进制 优化


    
    代码:
   
    [cpp]
   
    <span style=“font-family:FangSong_GB2312;font-size:18px;”>
   
    #include<iostream>
   
    using namespace std;
   
    int f[1200005];
   
    int c ;
   
    int main()
   
    {
   
    int i,j,k,t=1,cnt,sum,mount;
   
    while(1)
   
    {
   
    cnt=0;
   
    for(i=1;i<=6;i++)
   
    {
   
    scanf(“%d”,&c[i]);
   
    cnt+=c[i]*i;
   
    }
   
    if(cnt==0) {break;}
   
    printf(“Collection #%d:\n”,t++);
   
    if(cnt%2) {printf(“Can't be divided.\n”);printf(“\n”);continue;}
   
    sum=cnt/2;
   
    memset(f,0,sizeof(f));
   
    f[0]=1;
   
    for(i=1;i<=6;i++)
   
    {
   
    mount=c[i];
   
    for(k=1;k<=mount;k《=1)
   
    {
   
    for(j=cnt;j>=k*i;j--)
   
    f[j]+=f[j-k*i];
   
    mount-=k;
   
    }
   
    if(mount)
   
    for(j=cnt;j>=mount*i;j--) f[j]+=f[j-mount*i];
   
    }
   
    if(f[sum]) printf(“Can be divided.\n”);
   
    else printf(“Can't be divided.\n”);
   
    printf(“\n”);
   
    }
   
    return 0;
   
    }
   
    </span>

      

首页 上一页 1 2 3 下一页 尾页 3/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇关于c++中虚函数和接口的关系区分 下一篇POJ 2135 Farm To..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: