5
HDU1171 Big Event in HDU（01背包）
source link: https://arminli.com/hdu1171/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
HDU1171 Big Event in HDU（01背包）
March 09, 2016
题意：n 个设备，每个设备一行代表价值和数量，要求把所有设备分给两个学院，各个的价值和尽可能接近。
把总价值 sum 的一半看作 01 背包的容量，尽可能的往里放，可以求出较小的那个学院的总价值。
这题注意下数据范围和跳出情况，实际与题目描述不符。
如果 sum 在 01 背包前就除以 2 了，算较大的价值和再用 sum*2 算就错了，因为 sum/2*2 可能不等于 sum。
#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[255555];
int a[5005];
int main(){
//freopen("a.txt", "r", stdin);
int n, m;
while(~scanf("%d", &n) && n>0){
memset(dp, 0, sizeof(dp));
int cnt = 1, sum = 0;
for(int i = 1; i <= n; i++){
int x, y;
scanf("%d %d", &x, &y);
for(int j = 0; j < y; j++){
a[cnt++] = x;
sum += x;
}
}
for(int i = 1; i < cnt; i++){
for(int j = sum/2; j >= a[i]; j--)
dp[j] = max(dp[j], dp[j-a[i]]+a[i]);
}
cout << sum-dp[sum/2] << " " << dp[sum/2] <<endl;
}
return 0;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK