问题描述
小易有n块砖块,每一块砖块有一个高度。小易希望利用这些砖块堆砌两座相同高度的塔。为了让问题简单,砖块堆砌就是简单的高度相加,某一块砖只能使用在一座塔中一次。小易现在让能够堆砌出来的两座塔的高度尽量高,小易能否完成呢。
输入描述
输入包括两行:
第一行为整数n(1 ≤ n ≤ 50),即一共有n块砖块
第二行为n个整数,表示每一块砖块的高度height[i] (1 ≤ height[i] ≤ 500000)
输出描述
如果小易能堆砌出两座高度相同的塔,输出最高能拼凑的高度,如果不能则输出-1.
保证答案不大于500000。
输入例子
3
2 3 5
输出例子
5
分析
很容易联想到01背包问题。如果两座塔的高度都等于所有砖块总高度sum的一半,那么两座塔的高度最高。但是很遗憾,不是每个砖块都会被用到,所以01背包没法解决这个问题。
继续延续动态规划的思路。加上两座塔分别被命名为A和B。我们建立一个状态表dp[i][j]:i={0,1},表示上下状态行,用来压缩状态空间;j为两座塔的高度差B-A,我们会始终保证这个值为非负数,所以需要把j整体偏移sum,即[-sum,sum]+sum-->[0,2*sum];dp[i][j]为状态行i下,高度差B-A=j时,B的最大高度。
1. Base
dp[0][sum] = 0,即当没有放砖块,并且B-A为sum-sum=0(考虑之前的偏移)时,B的最大高度为0
2. Transition Function
dp[i][j]=max(dp[!i][j], dp[!i][j - h], dp[!i][j + h] + h)
dp[!i][j]表示不放该砖块;
dp[!i][j - h]表示把砖块放到A塔上;
dp[!i][j + h] + h表示把砖块放到B塔上。
3. result
dp[i][sum]
note
动态规划的状态转移方程有时候真的很难找