1: public static int stackHeight(ArrayList<Box> boxes) {
2: if (boxes == null) {
3: return 0;
4: }
5: int h = 0;
6: for (Box b : boxes) {
7: h += b.height;
8: }
9: return h;
10: }
11:
12: public static ArrayList<Box> createStackR(Box[] boxes, Box bottom) {
13: int max_height = 0;
14: ArrayList<Box> max_stack = null;
15: for (int i = 0; i < boxes.length; i++) {
16: if (boxes[i].canBeAbove(bottom)) {
17: ArrayList<Box> new_stack = createStackR(boxes, boxes[i]);
18: int new_height = stackHeight(new_stack);
19: if (new_height > max_height) {
20: max_stack = new_stack;
21: max_height = new_height;
22: }
23: }
24: }
25:
26: if (max_stack == null) {
27: max_stack = new ArrayList<Box>();
28: }
29: if (bottom != null) {
30: max_stack.add(0, bottom);
31: }
32:
33: return max_stack;
34: }
35:
36: public static ArrayList<Box> createStackDP(Box[] boxes, Box bottom, HashMap<Box, ArrayList<Box>> stack_map) {
37: if (bottom != null && stack_map.containsKey(bottom)) {
38: return stack_map.get(bottom);
39: }
40:
41: int max_height = 0;
42: ArrayList<Box> max_stack = null;
43: for (int i = 0; i < boxes.length; i++) {
44: if (boxes[i].canBeAbove(bottom)) {
45: ArrayList<Box> new_stack = createStackDP(boxes, boxes[i], stack_map);
46: int new_height = stackHeight(new_stack);
47: if (new_height > max_height) {
48: max_stack = new_stack;
49: max_height = new_height;
50: }
51: }
52: }
53:
54: if (max_stack == null) {
55: max_stack = new ArrayList<Box>();
56: }
57: if (bottom != null) {
58: max_stack.add(0, bottom);
59: }
60: stack_map.put(bottom, max_stack);
61:
62: return (ArrayList<Box>)max_stack.clone();
63: }
64:
65:
66: public static void main(String[] args) {
67: Box[] boxes = { new Box(1, 7, 4), new Box(2, 6, 9), new Box(4, 9, 6), new Box(10, 12, 8),
68: new Box(6, 2, 5), new Box(3, 8, 5), new Box(5, 7, 7), new Box(2, 10, 16), new Box(12, 15, 9)};
69:
70: //ArrayList<Box> stack = createStackDP(boxes, null, new HashMap<Box, ArrayList<Box>>());
71: ArrayList<Box> stack = createStackR(boxes, null);
72: for (int i = stack.size() - 1; i >= 0; i--) {
73: Box b = stack.get(i);
74: System.out.println(b.toString());
75: }
76: }
77:
78: public class Box {
79: public int width;
80: public int height;
81: public int depth;
82: public Box(int w, int h, int d) {
83: width = w;
84: height = h;
85: depth = d;
86: }
87:
88: public boolean canBeUnder(Box b) {
89: if (width > b.width && height > b.height && depth > b.depth) {
90: return true;
91: }
92: return false;
93: }
94:
95: public boolean canBeAbove(Box b) {
96: if (b == null) {
97: return true;
98: }
99: if (width < b.width && height < b.height && depth < b.depth) {
100: return true;
101: }
102: return false;
103: }
104:
105: public String toString() {
106: return "Box(" + width + "," + height + "," + depth + ")";
107: }
108: }