HDU 1171 Big Event in HDU 多重背包 .

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1171

就是把总价值分成一半，求最多能放多少

多重背包代码：842MS

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
int v[50+5],n[50+5];
bool d[250000+5];
//d[i] 表示i空间内 能否放到 
int main()
{int N; while(cin>>N,N>=0){int sum=0,half;for(int i=1;i<=N;i++){scanf("%d%d",&v[i],&n[i]);sum+=v[i]*n[i];}half=sum/2;int ans=0;memset(d,false,sizeof(d)); d[0]=true;for(int i=1;i<=N;i++)for(int j=0;j<n[i];j++)for(int k=half;k>=v[i];k--)if(d[k-v[i]]) d[k]=true,ans=max(ans,k);cout<<sum-ans<<' '<<ans<<endl;}return 0;	
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
int V[50+5];
bool d[500000+5];
//d[i] 表示i空间内 能否放到 
int main()
{int N,v,n; while(cin>>N,N>=0){int sum=0,half,p=0;for(int i=1;i<=N;i++){scanf("%d%d",&v,&n);for(int i=1;i<=n;i++)V[p++]=v,sum+=v;}half=sum/2;int ans=0;memset(d,false,sizeof(d)); d[0]=true;for(int i=0;i<p;i++)for(int k=half;k>=V[i];k--)if(d[k-V[i]]) d[k]=true,ans=max(ans,k);cout<<sum-ans<<' '<<ans<<endl;}return 0;	
}

多重背包二进制优化：78MS

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
int v[50+5],n[50+5];
bool d[250000+5];
//d[i] 表示i空间内 能否放到 
int main()
{int N; while(cin>>N,N>=0){int sum=0,half;for(int i=1;i<=N;i++){scanf("%d%d",&v[i],&n[i]);sum+=v[i]*n[i];}half=sum/2;int ans=0;memset(d,false,sizeof(d)); d[0]=true;for(int i=1;i<=N;i++){int c=n[i],k=1;while(c>k){for(int j=half;j>=k*v[i];j--)if(d[j-k*v[i]]) d[j]=true,ans=max(ans,j);c-=k; k<<=1;}for(int j=half;j>=c*v[i];j--)if(d[j-k*v[i]]) d[j]=true,ans=max(ans,j);}cout<<sum-ans<<' '<<ans<<endl;}return 0;	
}