小易有n块砖块，每一块砖块有一个高度。 小易希望利用这些砖块堆砌两座相同高度的塔。 为了让问题简单，砖块堆砌就是简单的高度相加， 某一块砖只能使用在一座塔中一次。 小易现在让能够堆砌出来的两座塔的高度尽量高，小易能否完成呢。 输入描述: 输入包括两行： 第一行为整数n(1 ≤ n ≤ 50)，即一共有n块砖块 第二行为n个整数，表示每一块砖块的高度height[i] (1 ≤ height[i] ≤ 500000) 输出描述: 如果小易能堆砌出两座高度相同的塔，输出最高能拼凑的高度，如果不能则输出-1. 保证答案不大于500000。 输入例子: 3 2 3 5 输出例子: 5
public class 搬砖块 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int []a=new int [n]; int sum=0; for(int i=0;i<n;i++){ a[i]=sc.nextInt(); sum+=a[i]; } sc.close(); //假设砖块分为A，B两堆，dp[i]中i表示B-A，所以dp长度为2*sum+1 // 滚动数组是对动态规划的的优化，把新数据替换旧数据形成滚动，节约内存空间 int[]dp0=new int[sum*2+1];//旧状态 int[]dp1=new int[sum*2+1];//新状态 Arrays.fill(dp0, -1);//A和B堆不一样高的情况均赋值-1。 dp0[sum]=0;//sum为偏移量 for(int i=0;i<n;i++){ int v=a[i]; for(int j=0;j<2*sum+1;j++){ dp1[j]=dp0[j]; if(j-v>=0){//将砖块放在低堆上 if(dp0[j-v]!=-1){ dp1[j]=Math.max(dp0[j-v], dp1[j]);//高度差减少，但高堆高度不变 } } if(j+v<=2*sum){//将砖块放在高堆上 if(dp0[j+v]!=-1){ dp1[j]=Math.max(dp0[j+v]+v, dp1[j]);//高度差增加，且高堆高度更高 } } } //交换dp，让dp0始终代表dp[i-1][j]的状态 int []tmp=dp1; dp1=dp0; dp0=tmp; } if(dp0[sum]==0){ System.out.println(-1); }else{ System.out.println(dp0[sum]); } } }