**joj 1903 tug of war 使用动态规划

 1903: Tug of War

---

Result TIME Limit MEMORY Limit Run Times AC Times JUDGE

	15s	8192K	556	123	Standard

A tug of war is to be arranged at the local office picnic. For the tug of war, the picnickers must be divided into two teams. Each person must be on one team or the other; the number of people on the two teams must not differ by more than 1; the total weight of the people on each team should be as nearly equal as possible.

The first line of input contains n the number of people at the picnic. n lines follow. The first line gives the weight of person 1; the second the weight of person 2; and so on. Each weight is an integer between 1 and 450. There are at most 100 people at the picnic.

The input may contain several test cases.

Your output will be a single line containing 2 numbers: the total weight of the people on one team, and the total weight of the people on the other team. If these numbers differ, give the lesser first.

Sample Input

3
100
90
200

Output for Sample Input

190 200

/*
	使用动态规划计算tug of war 
	其实动态规划类似于搜索
	搜索所有可能的状态，分辨哪些是可达的
*/
#include<iostream>  
using namespace std;  
int n,w[103],sum,ans,l,r;  
bool dp[45005][103];  //row:表示重量 col:表示人数
int main()  
{  
	int i;
   // freopen("in.txt","r",stdin);  
	//freopen("car.out","w",stdout); 
	while(scanf("%d", &n) != EOF)
	{
		memset(dp, 0, sizeof(dp));  
		 
		sum=0;  
		for(i=1;i<=n;i++)
			scanf("%d",&w[i]),sum+=w[i];  
		dp[0][0]=1; //表明体重是0 人数是0这个状态是可达的
		dp[0][101]=1;//人数最多是100，所以此时也是可达的
		/*
			下面两重循环首先计算出dp[w[i]][101] = 1,然后在向上累加
		*/
		for(i=1;i<=n;++i)  //人数开始循环
			for(int j=sum;j>=w[i];--j)  //体重开始循环，倒着推，可以避免重复计算？？？
				if(dp[j-w[i]][101])  
				{  
					dp[j][101]=1;  //如果dp[j-w[i]][101]可达，那么增加体重后dp[j][101]=1一定可达
					/*
						如果dp[0][0]可达，那么dp[w[i]][1]可达，
						所以如果dp[j-w[i]][k]可达，那么增加体重（同时也要增加人数）的dp[j][k+1]=1;  一定可达
					*/
					for(int k=0;k<n;k++)  
						if(dp[j-w[i]][k])
							dp[j][k+1]=1;  
				}  
		ans=sum/2; //最理想的状况是sum的一半 
		while(!(dp[ans][101] && (dp[ans][n/2] || dp[ans][(n+1)/2]))) //如果此时状态不可达，那么ans减小
			--ans;  
		printf("%d %d\n",ans,sum-ans);  				
	}
	return 0;  
}  

这种方法有局限性，只能适用于给数数据的上限，比如最多100人，每个人的体重最大450.如果没有这种限制，则不能使用dp。可以使用随机方法