Big Event in HDU
这道题是让我们将设备根据价值尽可能地平均分成两半，其实就是把设备的价值总和平分成两个部分，然后以此为背包，将这个背包尽可能填满。因为这里的“体积”和“价值”都是设备的价值，所以其实就是求价值的最大值。题目还要求输出时，大的在前面，小的在后面，这可以利用整除的特性做到，因为一个整数a整除2得到的结果一定是小于或等于a/2(非整除)的。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <algorithm>
using namespace std;
int v[5005];
int dp[1000000];
int ()
{
int n;
while(scanf("%d",&n)!=EOF&&n>0)
{
memset(dp,0,sizeof(dp));
memset(v,0,sizeof(v));
int half=0;
int idx=1;
for(int i=1;i<=n;i++)
{
int val,temp;
scanf("%d %d",&val,&temp);
while(temp--)
{
v[idx++]=val;
half+=val;
}
}
int tmp=half;
half/=2;
for(int i=1;i<idx;i++)
for(int j=half;j>=v[i];j--)
dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
int a,b;
a=tmp-dp[half];
b=dp[half];
cout<<a<<" "<<b<<endl;
}
return 0;
}
|
近期评论