HDU1171 Big Event in HDU(01背包)

题目链接

题意: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;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 01背包  动态规划