HDU 1171 Big Event in HDU（DP）

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <stdlib.h>
#include <algorithm>

using namespace std ;

struct node
{
    int value ;
    int num ;
}map[55] ;
int dp[251000] ;

int main()
{
    int n ;
    while(~scanf("%d",&n) && n >= 0)
    {
        int sum = 0 ;
        for(int i = 0 ; i < n ; i++)
        {
            scanf("%d %d",&map[i].value,&map[i].num) ;
            sum += map[i].value * map[i].num ;
        }
        int mid = sum >> 1 ;
        memset(dp,0,sizeof(dp)) ;
        for(int i = 0 ; i < n ; i ++)
        {
            for(int j = 0 ; j < map[i].num ; j++)
            {
                for(int k = mid ; k >= map[i].value ; k--)
                {
                    if(dp[k] < dp[k-map[i].value]+map[i].value)
                    dp[k] = dp[k-map[i].value]+map[i].value ;
                }
            }
        }
        printf("%d %d\n",sum-dp[mid],dp[mid]) ;
    }
    return 0 ;
}