HDU 1171（dp46）

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; int dp[500000]; int value[1005]; int number[1005]; int MidSum; int Sum; int i; void Complete()//完全背包 { int j; for(j=value[i];j<=MidSum;j++) dp[j]=max(dp[j],dp[j-value[i]]+value[i]); } void Mutiple()//次题数据较小不需要用二进制优化 { int j,k; for(j=1;j<=number[i];j++) for(k=MidSum;k>=value[i];k--) dp[k]=max(dp[k],dp[k-value[i]]+value[i]); } int main() { int N; while(scanf("%d",&N)) { memset(dp,0,sizeof(dp)); Sum=0; if(N<0)//小于零结束 return 0; for(i=1;i<=N;i++) { scanf("%d%d",&value[i],&number[i]); Sum+=value[i]*number[i];//记录总值 } MidSum=Sum/2;//注意Sum-MidSum>=MidSum; for(i=1;i<=N;i++) { if(value[i]*number[i]>MidSum)//相乘大于则相当于无穷多 { Complete(); } else//其他相当于有限个 { Mutiple(); } } printf("%d %d\n",Sum-dp[MidSum],dp[MidSum]);//注意先后顺序 } return 0; }