垒砖问题（转自Topcoder）
问题：现有高度各不同的一堆砖，现要求将其垒成两个高度相同的台子
输入：int [] bricks(各砖高度)
输出：int(有方案则输出台子高度，没有则为-1)
例如：
{ 2, 3, 5 }
Returns: 5
{ 10, 9, 2 }
Returns: -1
下面是我找到的一位牛人的算法，但是看不懂
- Java code
public class EqualTowers { /** * @param args the command line arguments */ private static final int MAX=250000; private int[][] mem= new int[50][MAX+1]; private int[] bricks; public int height(int[] bricks){ this.bricks=bricks; return go(0,0); } public int go(int k,int t){ if(t>MAX){ return -1; } if(k==bricks.length) { return ((t==0)?0:-1); } if(mem[k][t]==0){ //add to the First tower int d1=go(k+1,t+bricks[k]); //do nothing; int d2=go(k+1,t); //add to the second tower int d3=go(k+1,Math.abs(bricks[k]-t)); if(d3!=-1){ d3+=Math.min(t,bricks[k]); } //pick the best result mem[k][t]=Math.max(d1,Math.max(d2, d3)); //Prevent a 0-size tower in the final result; if(t==0&&k==0&&mem[k][t]==0){ mem[k][t]=-1; } mem[k][t]+=2; } return mem[k][t]-2; } public static void main(String[] args) { // TODO code application logic here }}欢迎讨论！
[解决办法]
先把所有砖块的高度总和/2=s2.
然后循环求砖块高度数组中的无序组合
如从2，3，5中选两个，结果有：2 ，3 2 ，5 3， 5 三种组合
在把求的组合之和于s2比较相等则输出；
- C# code
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int[] array ={ 2,3,5,8,9,7,0,34,29,11};
int n=4;
Method(array,n);
}
public static void Method(int[] arr, int N)
{
int[] prt = new int[100];
int s2=0;
for (int i = 0; i < prt.Length; i++)
{
prt[i] = -9999;
}
for(int i=0;i <arr.Length;i++)
{
s2+=arr[i];
}
s2/=2;
bool flog=fasle;
for (int i = 0; i < arr.Length; i++)
{
int prti = 0;
int k;
for (k = i; k < N + i - 1; k++, prti++)
{
prt[prti] = arr[k];
}
for (int j = k; j < arr.Length; j++)
{
prt[prti] = arr[j];
int s2test=0;
foreach (int u in prt)
{
if (u == -9999) break;
s2test+=prt[u];
}
if(s2==s2test)
{
Console.Write("{0}\t", s2test);
flog=true; break;
}
}
if (i + N == arr.Length) break;
if(flog==fasle) Console.Write("-1");
}
Console.ReadLine();
}
}
}
[解决办法]
假如bricks中放着,a,b,c,d 5个数.
我设一HashMap <Integer,Integer> (这个java中的类)
依次对bricks中的每一个数做以下运算：
如果HashMap中包含bricks[i]，则算法结束。否则把bricks[i]与HashMap中的各个数相加，并看看结果是否包含在HashMap中，如果是算法结束，否则把放入HashMap.再把brichs[i]放入HashMap.
第一次:HashMap：a.
第二次:HashMap: a,b+a,b
第三次：HashMap: a,b+a,b,c+a,c+b+a,c+b,c
第四次：HashMap: a,b+a,b,c+a,c+b+a,c+b,c,d+a,d+b+a,d+b,d+c+a,d+c+b+a,d+c+b,d+c,d
[解决办法]
楼主找到的程序，我给加了注释，希望大家都能看得懂。
- Java code
public class EqualTowers { /** * @param args the command line arguments */ private static final int MAX=250000; private int[][] mem= new int[50][MAX+1]; private int[] bricks; public int height(int[] bricks){ this.bricks=bricks; return go(0,0); } /** * * @param k 垒第k+1块砖(数组下标从0开始)。 * @param t 两座塔的高度差的绝对值。 * @return 有解时，返回较矮塔高度的最大值。在塔顶，两塔高度差为零，此时的返回值即为最终结果。 * 无解时，返回-1。 */ public int go(int k,int t){ // 高度差的值超出了此程序设计的缓存能力。 if(t>MAX){ return -1; } // 所有砖块垒好后，根据高度差的值判断是否有解。 if(k==bricks.length) { return ((t==0)?0:-1); } // 如果mem[k][t]==0，意味着go[k][t]是第一次被调用。 // 否则直接从mem[k][t]中读取第一次调用的计算结果。 // 这是为了提高递归算法效率而采取的一种常用技巧。 if(mem[k][t]==0){ // 将第k+1块砖垒到较高的塔上，由于之前两塔高度差为t，因此此次操作后高度差变成t+bricks[k]。 // 此操作对于较矮的塔的高度没有影响。 int d1=go(k+1,t+bricks[k]); // 舍弃第k+1块砖，高度差没有变化。 // 此操作对于较矮的塔的高度没有影响。 int d2=go(k+1,t); // 将第k+1块砖垒到较矮的塔上，高度差变成abs(bricks[k]-t)。 int d3=go(k+1,Math.abs(bricks[k]-t)); if(d3!=-1){ // 如果方案可行，从最后一块砖开始垒，同时计算当前较矮的塔的高度。 // 放置第k+1块砖之前，两塔高度分别为d3, d3+t; // 放置第k+1块砖之后，两塔高度分别为d3+bricks[k],d3+t; // 此时，较矮的塔高度为d3+min(t,bricks[k])。 d3+=Math.min(t,bricks[k]); } // 选取最佳结果 mem[k][t]=Math.max(d1,Math.max(d2, d3)); // 所有砖块都被舍弃的情况，无解。 if(t==0&&k==0&&mem[k][t]==0){ mem[k][t]=-1; } // 将计算的结果保存到mem数组中，考虑到 // mem[k][t]==d1==d2==d3==0 // mem[k][t]==d1==d2==d3==-1 // 两种情况，为了保证下次调用时m[k][t]不为0，所以在现有值的基础上加2。 mem[k][t]+=2; } return mem[k][t]-2; } public static void main(String[] args) { // TODO code application logic here }}
[解决办法]
还是背包问题，就是一个sum/2的背包，LZ给出的牛人的方法似乎是用状态压缩的动态规划解的，
应该是个不错的办法，不过不知道原题是否有些额外的条件，程序中定义的数组似乎有点小。
另外可以看看这个帖子，最近这个问题讨论了好多次了。从C版到C#版，还有算法版，题目都是找Sum/2大小的背包。
只不过这道题是要找刚好装满Sum/2的背包，剩下几道是找最接近Sum/2的，相比，这道题还要简单一些。
http://topic.csdn.net/u/20090511/23/a482be66-6598-46fa-be19-e7e356e2244b.html
[解决办法]