【动态规划】 EOJ 3338 双塔问题

Time limit per test: 1.0 seconds

Memory limit: 256 megabytes

Alice 和 Bob 在玩积木游戏。

他们找到了 n 块积木，这些积木都是正方体，棱长分别为 a1,a2,…,an。现在 Alice 和 Bob 要用这些积木垒两座高塔。他们想要这两座高塔的高度相等。问最大高度可能是多少？

摆放积木的顺序没有要求。两座高塔不能公用积木。

Input

第一行一个整数 n 。

第二行 n 个整数，用空格隔开，分别是 a1,a2,…,an(ai≥1,∑ni=1ai≤10 000)。

数据点规模约定：

• 对于 30% 的数据，1≤n≤15。
• 对于 100% 的数据，1≤n≤100。

Output

输出一个整数，表示最大高度。

如果不能完成任务，输出 0。

简化问题：

给你一堆正整数，选择其中的一些数，分成两部分，且每部分和相同。 问这个最大的和是多少。

例如： 2 3 3 3 6 8  —— 3+8 = 2 + 3 + 6 = 11 是最大的

           4 2 2 1 1 —— 4 + 1 = 2 + 2 + 1 = 5 是最大的。

【分析】：

思路一（显而易见）、把数分为堆1和堆2，直觉上可以写出状态转移F[i][j] = F[i-h[p]] | F[i][j-h[p]],

其中p表示第p个数字，F[i][j]i表示是否存在第一堆的和为i第二堆的和为j的情况。

然后找最大的i==j且F[i][j] != 0 ，i即为答案。然而对于最大和可以到10^8显然是不行的。

思路二、我们似乎不能表示所有和的种类情况，10^8的数据量巨大，但是观测到每个元素的值<= 10000， 100*10000似乎是能够接受的时间复杂度，该怎么利用这个条件？假象现在是人工操作，在分配数字的时候不可能让某一堆的值与另一堆的值的差，超过了每个数字的最大值。在这种情况下的决策必定是把这个数放在位置不同的那一堆里。

于是我们可以像这样定义状态：

1、F[i][j] 到第i个物品为止，两堆数字差的绝对值为j情况下最大的和。这个状态是符合时间空间预期复杂度的。

显然有F[i][j] = max{F[0~i-1][j-h[i]] + h[i]} 当 j > h[i] ，也就是说把当前这块积木放在原本就高的地方。

2、若有j <= h[i] F[i][j] = {F[0~i-1][h[i]-j] + j]   也就是把这块积木放在矮的地方，然而因为矮的地方在新积木的作用下比原本高的积木高了，又由于状态的定义，我们可以知道：现在的高度 - j = 原来的高度 ，也就是F[k][h[i]-j] + j

3、考虑另外一种情况，本来实力相差很悬殊了，但是由于这一块方块的加入，让差距减少了，但是最高值不变。也就是：

    F[i][j] = max{F[0~i-1][j+h[k]]}

好了状态转移结束，可以写代码了，其实不难

#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
const int limit = 10000;
int n = 0;
int dp[maxn][limit+maxn];
int h[maxn];
int main()
{
	int n = 0;
	cin >> n;
	for (int i = 1 ; i <= n ; ++i)
		cin >> h[i];
	memset(dp,-1,sizeof(dp));
	dp[0][0] = 0;	
	for (int i = 1 ; i <= n ; ++i)
	  for (int k = 0 ; k < i ; ++k) 
		for (int j = 0 ; j <= limit ; ++j)
		{
			if(j - h[i] >= 0 && dp[ k ][ j - h[i] ] != -1)
				dp[i][j] = max(  dp[ k ][ j - h[i] ] + h[i], dp[i][j]  );
				
			if(h[i] - j >= 0 && dp[ k ][ h[i] - j ] != -1)
				dp[i][j] = max(dp[ k ][ h[i] - j ] + j , dp[i][j]);
				
			if(h[i] + j <= limit && dp[ k ][ h[i] + j ] != -1)
				dp[i][j] = max(dp[ k ][ h[i] + j ] , dp[i][j]);
			if(dp[i][j] != 0)
			{
				int k = dp[i][j];
//				cout << k << endl;
			}
		}
	
	int ans = 0;
	for (int i = 1 ; i <= n ; ++i)
		ans = max(ans,dp[i][0]);
	cout << ans << endl; 
		
	
	return 0;
}