hdu 1171 Big Event in HDU(親関数|多重リュックサック)

http://acm.hdu.edu.cn/showproblem.php?pid=1171
題意:n種類の物品があり、それぞれの物品の価値と数を与え、これらの物品をできるだけ等しい2部のAとBに分け、A>=B、出力A、Bとする.
母関数は通過できますが、最も直接的な方法は多重リュックサックだと思います.
母関数も総価値の半分で求め,半分から小列挙,係数が0でないものを見つけるまでBである.

#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;

int main()
{
	int n;
	int val[55],num[55];
	int sum;
	int c1[125010],c2[125010];

	while(~scanf("%d",&n))
	{
		if(n < 0) break;

		sum = 0;
		for(int i = 1; i <= n; i++)
		{
			cin >> val[i] >> num[i];
			sum += val[i]*num[i];
		}

		int tmp = sum/2;

		memset(c1,0,sizeof(c1));
		memset(c2,0,sizeof(c2));

		for(int i = 0; i <= val[1]*num[1]; i += val[1])
			c1[i] = 1;

		for(int i = 2; i <= n; i++)
		{
			for(int j = 0; j <= tmp; j++)
			{
				for(int k = 0; k+j <= tmp && k <= val[i]*num[i]; k += val[i])
					c2[k+j] += c1[j];
			}
			for(int j = 0; j <= tmp; j++)
			{
				c1[j] = c2[j];
				c2[j] = 0;
			}
		}
		int i;
		for(i = tmp; i >= 0; i--)
			if(c1[i] != 0)
				break;

		printf("%d %d
",sum-i,i);

	}
	return 0;
}

多重リュックサックは、総価値の半分でリュックサックを行い、母関数よりも時間が速く、1次元よりも2次元の時間が速い.
最適化されていないマルチバックパック:

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int val[55],num[55];
int dp[125010];
int n;

int main()
{
	while(~scanf("%d",&n))
	{
		if(n < 0) break;

		int sum = 0;
		for(int i = 1; i <= n; i++)
		{
			scanf("%d %d",&val[i],&num[i]);
			sum += val[i]*num[i];
		}

		int tmp = sum/2;

		memset(dp,0,sizeof(dp));
		dp[0] = 1;
		int ans = -1;

		for(int i = 1; i <= n; i++)
		{
			for(int j = 0; j <= num[i]; j++)
			{
				for(int v = tmp; v >= j*val[i]; v--) //  
					if(dp[v-j*val[i]])
					{
						dp[v] = 1;
						ans = max(ans,v);
					}
			}
		}

		printf("%d %d
",sum-ans,ans);


	}
	return 0;
}