1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 437 - The Tower of Babylon
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=378
*
* @author Dennis Wilfert
* @version 1.0, 12/08/2009
*
* Methode: Größte aufsteigende Teilfolge
* Status : Accepted
* Runtime: 0.132
*/
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class TowersOfBabylon {

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));

StringTokenizer token;

int i, j, k, max, length;
int cases = 1;
int[][] blocks;
int[] sequenzes;
int[] temp;

int n = Integer.parseInt(reader.readLine());

while (n != 0) {

length = n * 3;
blocks = new int[length][3];
sequenzes = new int[length];

// Die Blöcke in jeder Lage in das Array eintragen
for (i = 0; i < length; i += 3) {
token = new StringTokenizer(reader.readLine());

blocks[i][0] = blocks[i + 1][2] = blocks[i + 2][1] = Integer.parseInt(token.nextToken());
blocks[i][1] = blocks[i + 1][0] = blocks[i + 2][2] = Integer.parseInt(token.nextToken());
blocks[i][2] = blocks[i + 1][1] = blocks[i + 2][0] = Integer.parseInt(token.nextToken());
}

// Mit Selection-Sort nach Länge und Breite aufsteigend sortieren
for (i = 0; i < length; i++) {
k = i;
for (j = i + 1; j < length; j++) {
if ((blocks[k][0] > blocks[j][0] && blocks[k][1] > blocks[j][1]) || (blocks[k][0] > blocks[j][1] && blocks[k][1] > blocks[j][0])) {
k = j;
}
}
// Werte tauschen
temp = blocks[k];
blocks[k] = blocks[i];
blocks[i] = temp;
sequenzes[i] = blocks[i][2];

}

// Aufsteigende Teilfolgen suchen
for (i = 0; i < length; i++) {
for (j = i + 1; j < length; j++) {
if ((sequenzes[j] < sequenzes[i] + blocks[j][2]) && ((blocks[j][0] > blocks[i][0] && blocks[j][1] > blocks[i][1]) || (blocks[j][0] > blocks[i][1] && blocks[j][1] > blocks[i][0]))) {
sequenzes[j] = sequenzes[i] + blocks[j][2];
}
}
}

// Größten Wert in sequenzes suchen, der größte Wert ist das Ergebnis
max = 0;
for (int z : sequenzes) {
if (max < z) {
max = z;
}
}

writer.printf("Case %d: maximum height = %d%n", cases++, max);


n = Integer.parseInt(reader.readLine());
}

writer.flush();
}
}

2.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 437 - The Tower of Babylon
* Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=378
*
* @author Kratzer Kevin
* @version 1.0, 11/04/2009
*
* Method : Backtracking
* Status : Timelimit
* Runtime: -
*/

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Formatter;
import java.util.Locale;
import java.util.Scanner;
public class Main437TimeLimit {
protected final BufferedReader input;
protected final BufferedWriter out;
private final int[][] combinations = new int[][] {{0,1,2},{0,2,1},{1,2,0}};
private final int combinationsLength = combinations.length;
private int maxScore = -1;
private int maxDim = -1;
private int minDim = -1;
public Main437TimeLimit() {
input = new BufferedReader(new InputStreamReader(System.in));
out = new BufferedWriter(new OutputStreamWriter(System.out));
}

void process() throws IOException {
Scanner s = new Scanner(input);
int number = 0;
for(int amount = s.nextInt(); amount != 0; amount = s.nextInt()) {
number++;
//int[][] input = new int[amount*3][3];
ArrayList<int[]> inputArray = new ArrayList<int[]>();
for(int i = 0; i < amount*3;i+=3) {
int nrOne = s.nextInt();
int nrTwo = s.nextInt();
int[] input = new int[] {Math.max(nrOne, nrTwo),Math.min(nrOne,nrTwo),s.nextInt()};
inputArray.add(input);
if(input[2] != input[1]) {
inputArray.add(new int[] {Math.max(input[0],input[2]),Math.min(input[0],input[2]),input[1]});
}
if(input[2] != input[1] && input[0] != input[2]) {
inputArray.add(new int[] {Math.max(input[1],input[2]),Math.min(input[1],input[2]),input[0]});
}
}
int[][] input = inputArray.toArray(new int[inputArray.size()][]);
maxScore = -1;

backtrack(input,0,Integer.MAX_VALUE,Integer.MAX_VALUE);
out.append("Case " + number + ": maximum height = " + maxScore + "\n");
out.flush();
}
out.flush();
}




private void backtrack(int[][] input, int score, int maxDim, int minDim) {
if(!(maxScore > score && (this.maxDim > maxDim && this.minDim > minDim))) {
for(int i = 0; i < input.length; i++) {
if(input[i][0] < maxDim && input[i][1] < minDim) {
backtrack(input,score+input[i][2],input[i][0],input[i][1]);
} else {
if(score > maxScore) {
maxScore = score;
this.maxDim = maxDim;
this.minDim = minDim;
}

}
}
}
}

public static void main(String... args) throws Exception {
new Main437TimeLimit().process();
}


}