hdu 1059二进制优化背包问题

#include<stdio.h>
#include<string.h>
int max(int a,int b ) {
 return a>b?a:b;
}
int a[8];
int dp[50000];
int main() {
    int i,j,m=0,sum,k,l;
    while(scanf("%d%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6])!=EOF) {
        m++;
             sum=a[1]*1+a[2]*2+a[3]*3+a[4]*4+a[5]*5+a[6]*6;
        if(!a[1]&&!a[2]&&!a[3]&&!a[4]&&!a[5]&&!a[6])
            break;
        printf("Collection #%d: ",m);
        memset(dp,0,sizeof(dp));
        if(sum%2==1) {
            printf("Can't be divided. ");
            continue;
        }
  for(i=1;i<=6;i++) {
   if(a[i]*i>sum/2) {
    for(j=i;j<=sum/2;j++)
     dp[j]=max(dp[j],dp[j-i]+i);
   }
    else {
         l=a[i];k=1;
      while(k<l) {
       for(j=sum/2;j>=k*i;j--)
        dp[j]=max(dp[j],dp[j-k*i]+k*i);
       l-=k;
       k*=2;
      }
       for(j=sum/2;j>=k*i;j--)
        dp[j]=max(dp[j],dp[j-l*i]+l*i);
    }
   }
                     if(dp[sum/2]==sum/2)
                         printf("Can be divided. ");
                     else
                         printf("Can't be divided. ");

    }
    return 0;
}
   

原文地址:https://www.cnblogs.com/bbsno1/p/3271269.html