首页 > 代码库 > hdu 1059 Dividing 多重背包

hdu 1059 Dividing 多重背包

就是看能不能装满给定容量的背包。

#include <stdio.h>#include <string.h>int dp[200000],a[15];int main(){    int cas=0,c;    int i,j,k;    while(1)    {        int sum=0;        cas++;        for(i=1;i<=6;i++)        {            scanf("%d",&a[i]);            sum+=a[i]*i;        }        if(sum==0) break;        printf("Collection #%d:\n",cas);        if(sum%2!=0)        {            printf("Can‘t be divided.\n\n");            continue;        }        sum/=2;        memset(dp,0,sizeof(dp));        dp[0]=1;        for(i=1;i<=6;i++)        {            if(a[i]==0) continue;            for(j=1;j<=a[i];j*=2)            {                c=j*i;                for(k=sum;k>=c;k--)                    if(dp[k-c])                        dp[k]=1;                a[i]-=j;            }            c=a[i]*i;            if(c!=0)            {                 for(k=sum;k>=c;k--)                    if(dp[k-c]) dp[k]=1;            }        }        if(dp[sum]) printf("Can be divided.\n\n");        else printf("Can‘t be divided.\n\n");    }    return 0;}