HDU 1171 Big Event in HDU（DP）

题意：给你一个n，然后n组数据，每组两个数字，一个是物品的价值，另外一个是物品的数量，让你尽量将这些东西分成价值相等的两份，如果无法相等就前一份要大于后一份。

思路：这个题可以转化成01背包的放与不放的问题，就是该题中最后一句要注意到是一个负数终结输出而非-1 ，就因为我没发现WA了8次。。。。真是郁闷了。

#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
",sum-dp[mid],dp[mid]) ;
    }
    return 0 ;
}

View Code

HDU 1171 Big Event in HDU（DP）

相关推荐