Big Event in HDU HDU1171
就是求一个简单的背包：
题意：就是给出一系列数，求把他们尽可能分成均匀的两堆
如：2 10 1 20 1 结果是：20 10。才最均匀！
三种解法：
多重背包的优化与否：（1031MS）
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int dp[];
int a[],b[];
int main()
{
int n,s,i,j,k;
while(scanf("%d",&n)!=EOF)
{
if(n<)
break;
s=;
for(i=;i<n;i++)
{
scanf("%d%d",&a[i],&b[i]);
s+=a[i]*b[i];
}
memset(dp,,sizeof(dp));
for(i=;i<n;i++)
for(j=;j<=b[i];j++)
for(k=s/;k>=a[i];k--)
dp[k]=max(dp[k],dp[k-a[i]]+a[i]);
if(dp[s/]>s-dp[s/])
printf("%d %d\n",dp[s/],s-dp[s/]);
else
printf("%d %d\n",s-dp[s/],dp[s/]);
}
return ;
}
二进制优化的：（46MS）
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
int dp[],a1[];
int main()
{
int a[],b[],n,i,j,k,s,cout1;
while(scanf("%d",&n)!=EOF)
{
if(n<)
break;
s=;
cout1=;
for(i=;i<n;i++)
{
scanf("%d%d",&a[i],&b[i]);
s+=a[i]*b[i];
for(k=;k<=b[i];k<<=)
{
a1[cout1++]=k*a[i];
b[i]-=k;
}
if(b[i]>)
a1[cout1++]=b[i]*a[i];
}
memset(dp,,sizeof(dp));
for(i=;i<cout1;i++)
for(j=s/;j>=a1[i];j--)
dp[j]=max(dp[j],dp[j-a1[i]]+a1[i]);
if(dp[s/]>=s-dp[s/])
printf("%d %d\n",dp[s/],s-dp[s/]);
else
printf("%d %d\n",s-dp[s/],dp[s/]);
}
return ;
}
最后是母函数求解的：（875MS）
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int c1[],c2[];
int main()
{
int n,i,j,k,s;
int a[],b[];
while(scanf("%d",&n)!=EOF)
{
s=;
if(n<)
break;
for(i=;i<=n;i++)
{
scanf("%d%d",&a[i],&b[i]);
s+=a[i]*b[i];
}
for(i=;i<=s;i++)
{
c1[i]=;
c2[i]=;
}
c1[]=;
for(i=;i<=n;i++)
{
for(j=;j<=s;j++)
for(k=;k+j<=s,k<=a[i]*b[i];k+=a[i])
c2[k+j]+=c1[j];
for(j=;j<=s;j++)
{
c1[j]=c2[j];
c2[j]=;
}
}
for(i=s/;i<=s;i++)
{
if(c1[i]!=)
break;
}
if(i>=s-i)//且要取最大值
printf("%d %d\n",i,s-i);
else
printf("%d %d\n",s-i,i);
}
return ;
}