hdu 1171 Big Event in HDU 母函数以及背包做法

Big Event in HDUTime Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13396    Accepted Submission(s): 4682


Problem DescriptionInputOutputSample InputSample OutputAuthor#include<stdio.h>#include<string.h>int c1[200000],c2[200000];int a[200],c[200];int main(){int n,i,j,sum,k;while(scanf("%d",&n)!=EOF){if(n<0) break ;sum=0;for(i=1;i<=n;i++){scanf("%d %d",&a[i],&c[i]);sum+=a[i]*c[i];}memset(c1,0,sizeof(c1));memset(c2,0,sizeof(c2));for(i=0;i<=a[1]*c[1];i+=a[1])//{c1[i]=1;}for(i=2;i<=n;i++){for(j=0;j<=sum;j++)for(k=0;k<=a[i]*c[i]&&k+j<=sum;k+=a[i])//不是k++ 而是加a[i]c2[k+j]+=c1[j];for(j=0;j<=sum;j++){c1[j]=c2[j];c2[j]=0;}}for(i=sum/2;i>0;i--){if(c1[i]!=0)break;}printf("%d %d\n",sum-i,i);}return 0;}
背包#include<stdio.h>#include<string.h>int bag[250000+5];int val[100000];int _01bag(int v,int m){ int i,j,max=0; memset(bag,0,(v+3)*sizeof(bag[0]));// printf("m=%d\n",m); for(i=0;i<m;i++) for(j=v;j>=val[i];j--) { if(bag[j]<bag[j-val[i]]+val[i]) bag[j]=bag[j-val[i]]+val[i]; if(max<bag[j]&&bag[j]<=v) max=bag[j]; } return max; }int main(){ int n,i,j,ge,va,temp,sum,ans; while(scanf("%d",&n)&&n>0) { j=0;sum=0; for(i=0;i<n;i++) { scanf("%d %d",&va,&ge); sum+=va*ge; temp=1; while(ge>temp) { val[j++]=temp*va; ge=ge-temp; temp=temp*2; } val[j++]=ge*va; } ans=_01bag(sum/2,j); // for(i=0;i<j;i++) // printf("%d\n",val[i]); printf("%d %d\n",sum-ans,ans); }}