http://acm.hdu.edu.cn/showproblem.php?pid=1171
這道題咋看有點(diǎn)復(fù)雜须板，其實(shí)也只是換了一種思維，因?yàn)轭}目要求要盡量平均分配，所以我們可以先將總價(jià)值sum求出，然后得出其分配的平均值為sum/2,要注意這個(gè)答案可能為小數(shù)，但是又因?yàn)閟um是整數(shù)价认，所以最后得出的sum/2是要小于等于實(shí)際的值。將這個(gè)結(jié)果進(jìn)行01,背包自娩，可以得出其中一個(gè)宿舍所得的最大價(jià)值用踩，而另一個(gè)宿舍的最大價(jià)值也可以相應(yīng)的得到，而前者必定小于等于后者椒功。
include<iostream>
include<cstring>
include<algorithm>
define INF 1000005
using namespace std;
int d[1005][1005];
int v[5005];
int main(){
int n;
while(cin >> n,n>0) {
int sum = 0;
for(int i = 1,k = 0;k < n;k++)
{
int e,f;
cin >> e >> f;
sum += e*f;
while(f--)
v[i++] = e;
}
for(int i = 1;i <= n;i++)
{
for(int j = 0;j <= sum/2;j++){
d[i][j] = (i == 1?0:d[i-1][j]);
if(j >= v[i])
d[i][j] = max(d[i][j],d[i-1][j-v[i]]+v[i]);
}
}
cout << sum - d[n][sum/2] << " " << d[n][sum/2] << endl;
memset(d,0,sizeof(d));
}
return 0;
}
