hdu 1171 Big Event in HDU 01背包

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=1171

題目大意：hdu的計算機分成兩個學院，現在有n種裝置，價值為vi的有mi個，要求把這些東西分成價值總和最為接近的兩份，如果不能平分，大的在前面。

//author: [email protected]
//因為每個設定的最大數量不大，是以可以使用01背包解出
//隻要求出以所有裝置總價值一半為容量的背包，能放入的最大價值即可

#include <stdio.h>
#include <string.h>

inline int max(int a, int b)
{
	return a > b ? a : b;
}

int main()
{
	int n;
	while(scanf("%d", &n) && n >= 0)
	{
		int v[51], m[51];
		int sum = 0;
		for(int i = 0; i < n; ++ i)
		{
			scanf("%d %d", &v[i], &m[i]);
			sum += v[i] * m[i];
		}

		int f[125001];
		int helf = sum / 2;

		memset(f, 0, sizeof(f));
		for(int i = 0; i < n; ++ i)
			for(int j = 0; j < m[i]; ++ j)
				for(int k = helf; k >= v[i]; -- k)
					f[k] = max(f[k], f[k - v[i]] + v[i]);
		int ava = f[helf];
		if(ava < sum - ava)
			ava = sum - ava;
		printf("%d %d\n", ava, sum - ava);
	}

	return 0;
}