HDU1171_Big Event in HDU【01リュック】
3244 ワード
Big Event in HDU
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 24321 Accepted Submission(s): 8562
Problem Description Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don't know that Computer College had ever been split into Computer College and Software College in 2002. The splitting is absolutely a big event in HDU! At the same time, it is a trouble thing too. All facilities must go halves. First, all facilities are assessed, and two facilities are thought to be same if they have the same value. It is assumed that there is N (0lcy
N種類の設備があって、それぞれの設備は1つの価値と数量があります.まずこのN種類の設備を総価値で
できるだけ平均して2つの学院に分けます.完全に平均点が取れなければ、最初の学院はもっと点数をつけます.
問、2つの学院はそれぞれどれだけの価値の設備を分けることができますか?
考え方:各設備には数量と価値があり、各設備を一つの物品とすることができる.例えば、第
1つの設備にはM件があり、価値がVであればM件の物品に変換され、価値はすべてVである.これで01に変換できます
リュックサックです.総価値の半分をリュックサック容量とする.最も多くどれだけの価値の物品を詰めることができることを求めます.できるだけ
分けられる上で最初の学院はもっと分けなければならない.結果は第一学院でsum-dp[sum/2]を得た.
第2学院はdp[sum/2]を得た.
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 24321 Accepted Submission(s): 8562
Problem Description Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don't know that Computer College had ever been split into Computer College and Software College in 2002. The splitting is absolutely a big event in HDU! At the same time, it is a trouble thing too. All facilities must go halves. First, all facilities are assessed, and two facilities are thought to be same if they have the same value. It is assumed that there is N (0
N種類の設備があって、それぞれの設備は1つの価値と数量があります.まずこのN種類の設備を総価値で
できるだけ平均して2つの学院に分けます.完全に平均点が取れなければ、最初の学院はもっと点数をつけます.
問、2つの学院はそれぞれどれだけの価値の設備を分けることができますか?
考え方:各設備には数量と価値があり、各設備を一つの物品とすることができる.例えば、第
1つの設備にはM件があり、価値がVであればM件の物品に変換され、価値はすべてVである.これで01に変換できます
リュックサックです.総価値の半分をリュックサック容量とする.最も多くどれだけの価値の物品を詰めることができることを求めます.できるだけ
分けられる上で最初の学院はもっと分けなければならない.結果は第一学院でsum-dp[sum/2]を得た.
第2学院はdp[sum/2]を得た.
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int V[5050],dp[250050];
int main()
{
int N,v,m,sum;
while(~scanf("%d",&N) && N>0)
{
int num = 0;
sum = 0;
memset(V,0,sizeof(V));
memset(dp,0,sizeof(dp));
for(int i = 0; i < N; i++)
{
scanf("%d%d",&v,&m);
while(m--)
{
V[num++] = v;
sum += v;
}
}
for(int i = 0; i < num; i++)
{
for(int j = sum/2; j >= V[i]; j--)
{
dp[j] = max(dp[j],dp[j-V[i]] + V[i]);
}
}
printf("%d %d
",sum-dp[sum/2],dp[sum/2]);
}
return 0;
}