程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 1171 Big Event in HDU(母函數|多重背包)

hdu 1171 Big Event in HDU(母函數|多重背包)

編輯：C++入門知識

hdu 1171 Big Event in HDU(母函數|多重背包)

題意：有n種物品，給出每種物品的價值和數目，要將這些物品盡可能的分成相等的兩份A和B且A>=B ,輸出A，B。

母函數可以過，但感覺最直接的方法應該是多重背包。

母函數的話，也是按總價值的一半求，從一半到小枚舉，直到找到系數不為0的就是B。

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#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;
}

多重背包，按總價值的一半進行背包，相比母函數時間更快，一維的相比二維的時間更快。

未優化的多重背包：

#include 
#include 
#include 
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;
}