hdu试题链接

文章目录

Problem Description

Nowadays, we all know that Computer College is the biggest department
in HDU. But, maybe you don’t know that Computer College had ever been
split into Computer College and Software College in 2002. The
splitting is absolutely a big event in HDU! At the same time, it is a
trouble thing too. All facilities must go halves. First, all
facilities are assessed, and two facilities are thought to be same if
they have the same value. It is assumed that there is N (0<N<1000)
kinds of facilities (different value, different kinds).

Input

Input contains multiple test cases. Each test case starts with a
number N (0 < N <= 50 – the total number of different facilities).
The next N lines contain an integer V (0<V<=50 --value of facility)
and an integer M (0<M<=100 --corresponding number of the facilities)
each. You can assume that all V are different. A test case starting
with a negative integer terminates input and this test case is not to
be processed.

Output

For each case, print one line containing two integers A and B which
denote the value of Computer College and Software College will get
respectively. A and B should be as equal as possible. At the same
time, you should guarantee that A is not less than B.

Sample Input

2
10 1
20 1
3
10 1 
20 2
30 1
-1

Sample Output

20 10
40 40

题意：

有n个物品，每个物品都有价值和个数，要把这些物品分成两份，尽可能使得这两份相等，如果不相同就要保证第一份不小于第二份。答案是分别输出两份的价值

题解：

混合背包的题目，我这篇讲hdu 1059 Dividing的题解几乎和这样是一样的，就是读入方式不一样，稍微改一改代码就可以
这可以当做是模板题吧，建议熟读（滑稽）

代码：

#include<bits/stdc++.h>
using namespace std;
int a[8];
int sum=0;
int dp[120005];
int v[140],m[120];
bool f=0;
void zerone(int cost,int val)
{
   
	for(int i=sum;i>=cost;i--)
	{
   
		dp[i]=max(dp[i],dp[i-cost]+val);
	}
	
}
void complet(int cost)
{
   
	for(int i=cost;i<=sum;i++)
	dp[i]=max(dp[i],dp[i-cost]+cost);
}
void mul(int cost,int val,int num)
{
   
	if(cost*num>=sum)
	{
   
		complet(cost);
		return ;
	}
	
	for(int i=1;i<=num;i<<=1)
	{
   
		zerone(i*cost,i*val);
		num-=i;
	}
	zerone(num*cost,num*val);
}
int main()
{
   
	int n;
	while(cin>>n&&n>=0)
	{
   
		int sum1;
		sum1=0;
			memset(dp,0,sizeof(dp));
				memset(v,0,sizeof(v));
					memset(m,0,sizeof(m));
		for(int i=1;i<=n;i++)
		{
   
			cin>>v[i]>>m[i];
			sum1+=v[i]*m[i];
		}
	sum=sum1/2;
		
		for(int i=1;i<=n;i++)
		{
   
			mul(v[i],v[i],m[i]);//花费，价值，数量 
		}
		sum=max(dp[sum],sum1-dp[sum]);
		cout<<sum<<" "<<sum1-sum<<endl;
	}
	return 0;
}
/* 2 10 1 20 1 3 10 1 20 2 30 1 -1 */