HDU 1171 Big Event in HDU [多重背包]

分手后的思念是犯贱 2022-05-29 10:24 293阅读 0赞 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <math.h>
  4. #include <algorithm>
  5. using namespace std;
  6. int ttt[5005];
  7. int dp[255555];
  8. int main(int argc, char *argv[])
  9. {
  10.     int n,a,b;
  11.     int sum,i,j,k;    
  12.     while(scanf("%d",&n)!=EOF&&n>0)
  13.     {
  14.         k=0;
  15.         sum=0;
  16.         memset(dp,0,sizeof(dp));
  17.         memset(ttt,0,sizeof(ttt));
  18.         for(i=0;i<n;i++)
  19.         {    
  20.             scanf("%d %d",&a,&b);
  21.             sum+=a*b;
  22.             while(b--)
  23.             {
  24.                 ttt[k++]=a;
  25.             }
  26.         }    
  27.         for(i=0;i<k;i++)
  28.         {
  29.             for(j=sum/2;j>=ttt[i];j--)
  30.                 dp[j]=max(dp[j],dp[j-ttt[i]]+ttt[i]);
  31.         }
  32.             printf("%d %d\n",sum-dp[sum/2],dp[sum/2]);
  33.     }
  34.     return 0;
  35. }

发表评论

表情：
评论列表 （有 0 条评论，293人围观）

还没有评论，来说两句吧...

相关阅读