This is an interesting maximization problem that can be solved efficiently, in O(n) time, using dynamic programming.
You’re given a list of houses, each with a money value assigned to it. The problem is to choose houses from the list so as to maximize the total money from them, but no two houses chosen can be adjacent.
I originally created a binary tree from the input data and recursively searched every possible combination of houses, but for a large number of houses the number of combinations exploded and my program never returned.
My source code can be downloaded here.
1 import java.util.ArrayList; 2 import java.util.Arrays; 3 import java.util.List; 4 import java.util.Random; 5 6 /** 7 * The problem: given a list of houses, each house with a certain money value associated with it, write an algorithm 8 * that computes the maximum money that can be obtained by picking houses such that no two chosen houses are adjacent 9 * to one another. 10 * <p/> 11 * Example input: {(H1, 2), (H2, 1), (H3, 2), (H4, 3), (H5, 2)} 12 * <p/> 13 * Expected output: {6, (H1, H3, H5)} 14 * <p/> 15 * The solution: use dynamic programming. Realize that the solution can be expressed by the following relationship: 16 * <p/> 17 * Solution for 1 house = S(1) = money value of house 1 = H1 18 * Solution for 2 houses = S(2) = max(H2, S(1)) 19 * S(3) = max(H3 + S(1), S(2)) 20 * ... 21 * S(n) = max(Hn + S(n - 2), S(n - 1)) 22 * 23 * @author Chip Killmar 24 */ 25 public class Houses { 26 public static void main(String[] args) throws Exception { 27 // Create some houses with random money values. 28 Random random = new Random(); 29 House[] houses = new House[5]; 30 for (int i = 0; i < houses.length; ++i) { 31 House house = new House(String.valueOf(i), random.nextInt(4)); 32 houses[i] = house; 33 } 34 System.out.println("Input=" + Arrays.toString(houses)); 35 36 System.out.println("Output=" + chooseHouses(Arrays.asList(houses))); 37 } 38 39 /** 40 * An O(n) algorithm that chooses the houses such that the total money value of the houses is maximized, with the 41 * constraint that no two houses chosen can be adjacent to each other. 42 * 43 * @param houses An array of input houses. 44 * @return The result as a 2-tuple of {Total Money, List of Houses}. 45 */ 46 private static Tuple2<Integer, List<House>> chooseHouses(List<House> houses) { 47 List<Tuple2<Integer, List<House>>> results = new ArrayList<Tuple2<Integer, List<House>>>(houses.size()); 48 49 for (int i = 0; i < houses.size(); ++i) { 50 if (i == 0) { 51 int money = houses.get(0).getMoney(); 52 53 List<House> housesResult = new ArrayList<House>(); 54 housesResult.add(houses.get(0)); 55 56 Tuple2<Integer, List<House>> result = new Tuple2<Integer, List<House>>(money, housesResult); 57 results.add(result); 58 } else if (i == 1) { 59 int money = houses.get(1).getMoney() > houses.get(0).getMoney() ? houses.get(1).getMoney() : houses.get(0).getMoney(); 60 61 List<House> housesResult = new ArrayList<House>(); 62 housesResult.add(houses.get(1).getMoney() > houses.get(0).getMoney() ? houses.get(1) : houses.get(0)); 63 64 Tuple2<Integer, List<House>> result = new Tuple2<Integer, List<House>>(money, housesResult); 65 results.add(result); 66 } else { 67 Tuple2<Integer, List<House>> previousPreviousResult = results.get(i - 2); 68 Tuple2<Integer, List<House>> previousResult = results.get(i - 1); 69 70 int previousMoney = previousResult.getFirst(); 71 int currentMoney = previousPreviousResult.getFirst() + houses.get(i).getMoney(); 72 73 Tuple2<Integer, List<House>> result; 74 if (currentMoney > previousMoney) { 75 List<House> housesResult = new ArrayList<House>(previousPreviousResult.getSecond()); 76 housesResult.add(houses.get(i)); 77 result = new Tuple2<Integer, List<House>>(currentMoney, housesResult); 78 } else { 79 result = new Tuple2<Integer, List<House>>(previousMoney, previousResult.getSecond()); 80 } 81 results.add(result); 82 } 83 } 84 85 return results.get(results.size() - 1); 86 } 87 88 private static class House { 89 private String name; 90 private int money; 91 92 public House(String name, int money) { 93 this.name = name; 94 this.money = money; 95 } 96 97 public String getName() { 98 return name; 99 } 100 101 public int getMoney() { 102 return money; 103 } 104 105 @Override 106 public String toString() { 107 final StringBuilder sb = new StringBuilder(); 108 sb.append("House"); 109 sb.append("{name='").append(name).append('\''); 110 sb.append(", value=").append(money); 111 sb.append('}'); 112 return sb.toString(); 113 } 114 } 115 116 private static class Tuple2<T, U> { 117 private T first; 118 private U second; 119 120 public Tuple2(T first, U second) { 121 if (first == null) { 122 throw new NullPointerException("first"); 123 } 124 if (second == null) { 125 throw new NullPointerException("second"); 126 } 127 128 this.first = first; 129 this.second = second; 130 } 131 132 public T getFirst() { 133 return first; 134 } 135 136 public U getSecond() { 137 return second; 138 } 139 140 @Override 141 public String toString() { 142 final StringBuilder sb = new StringBuilder(); 143 sb.append("Tuple2"); 144 sb.append("{first=").append(first); 145 sb.append(", second=").append(second); 146 sb.append('}'); 147 return sb.toString(); 148 } 149 } 150 }