机试算法讲解： 第53题 动态规划之如何摆放橘子

/*
问题:有一堆柑橘，重量为0到2000，总重量不大于2000。从中取出两堆放在扁担两头，且两头重量相等，问符合条件的的每堆重量最大是多少。没有符合条件的分堆方式则输出
     -1
输入:第一行时t,表示t个测试用例，对每个测试用例，包含一个数字n,表名橘子数。第二行有n个数字，表明每个橘子的重量，1<=n<=100.如果是因为存在重量为0的橘子，
     导致扁担两边重量为0，那么应该输出0,否则输出-1

思路:橘子放在第一堆或者第二堆造成两堆之间的重量动态变化，设dp[i][j]:表示第i个橘子放入后，第一堆比第二堆重j时，两堆的最大重量和
     初始状态:dp[0][0],dp[0][j](j!=0)为负无穷，表明其他状态不存在
	 目标状态:dp[n][0]/2即为所求。因为dp[n][0]表示的是总重量
	 橘子的3种摆放方式:放入第一堆，放入第二堆，不放入。设橘子重量为wei[i]
	 放入第一堆:dp[i][j]=dp[i-1][j+wei[i]]+wei[i]
	 放入第二堆:dp[i][j]=dp[i-1][j-wei[i]]+wei[i]
	 不放:      dp[i][j]=dp[i-1][j]

复杂度:总重量<=2000,时间复杂度=状态数量*状态转移复杂度=柑橘总数(n*2*2000)*O(1)=O(4000*m)，n表示橘子的数量，

输入:
1
5
1 2 3 4 5
输出:
7

关键:
1 注意重量可能为负，需要加偏置值2000
2 注意最后打印与判断是dp[n][0+OFFSET]/2.对于每个橘子，存在-2000到2000的共4000状态量的变化，所以转移值需要放在状态量变化那层循环中
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//设置偏置值
#define OFFSET  200
//设置橘子最大数量+1
#define N 101
//设置最大正整数
#define INT_MAX 0x7fffffff

int main(int argc,char* argv[])
{
	int dp[N][401];//用于保存当加入dp[i][j]=放入第i个橘子，造成第一堆比第二堆重量重j时两堆的最大总重量
	int wei[N];//保存橘子的重量
	int T;//表示测试用例数
	int n;//表示一共有多少个橘子
	int iCnt = 0,i,j;
	bool haveZero = false;
	while(EOF!=scanf("%d",&T))
	{
		//对于每个测试用例数，获取橘子信息，对于重量为0的橘子进行过滤，不做处理
		while(T--)
		{
			scanf("%d",&n);
			for(i = 0 ; i < n ; i++)
			{
				scanf("%d",&wei[++iCnt]);
				if(wei[iCnt]==0)
				{
					haveZero = true;
					iCnt--;//去除重量为0的橘子
				}
			}
		}
		//初始化无效的状态量
		for(j = -200; j <= 200 ; j++)
		{
			dp[0][j+OFFSET] = -INT_MAX;
		}
		//设置唯一的正确状态量,dp[0][2000]=0
		dp[0][0+OFFSET] = 0;
		n = iCnt;//更新重量不为0的橘子的数量

		//易错,开始进行状态转移,遍历每个柑橘，对每个柑橘，遍历每种状态量
		for(i = 1 ; i <= n ; i++)
		{
			for(j = -200 ; j <= 200 ; j++)
			{
				//易错，每放入一个橘子，重新设置总重量，记录放在第一堆时转移得来的总重量的新值，若为-INT_MAX，表示无法转移
				int iTemp1 = -INT_MAX,iTemp2 = -INT_MAX;
				//如果将橘子放入第一堆中，造成第一堆比第二堆的重量差 + wei[i],对是否超过总重量需要进行判断，对是否转移到无效状态进行判断
				//if(dp[i][ j+OFFSET+wei[i] ] <= 2000 && dp[][])
				if(j+wei[i] <= 200 && -INT_MAX!=dp[i-1][ j+wei[i]+OFFSET ])
				{
					iTemp1 = dp[i-1][j+wei[i]+OFFSET] + wei[i];
				}
				//如果放在第二堆
				if(j-wei[i] >= -200 && -INT_MAX!=dp[i-1][ j-wei[i]+OFFSET ])
				{
					iTemp2 = dp[i-1][j-wei[i]+OFFSET] + wei[i];
				}
				//取总重量重的较大值
				if(iTemp1 < iTemp2)
				{
					iTemp1 = iTemp2;
				}
				//与不放橘子的总重量进行比较
				if(iTemp1 < dp[i-1][j+OFFSET])
				{
					iTemp1 = dp[i-1][j+OFFSET];
				}

				//更新当前状态量为上述3个状态量中的最大的一个
				dp[i][j+OFFSET] = iTemp1;
			}//for
		}//for
		//如果总重量为0,注意加上偏置值
		//if(dp[n][0]==0)
		if(dp[n][0+OFFSET]==0)
		{
			puts(true==haveZero ? "0":"-1");
		}
		else
		{
			//易错,注意加上偏置值
			//printf("%d\n",dp[n][0]/2);
			printf("%d\n",dp[n][0+OFFSET]/2);
		}
	}
	system("pause");
	getchar();
	return 0;
}