import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Random; /** * The problem: given a list of houses, each house with a certain money value associated with it, write an algorithm * that computes the maximum money that can be obtained by picking houses such that no two chosen houses are adjacent * to one another. *

* Example input: {(H1, 2), (H2, 1), (H3, 2), (H4, 3), (H5, 2)} *

* Expected output: {6, (H1, H3, H5)} *

* The solution: use dynamic programming. Realize that the solution can be expressed by the following relationship: *

* Solution for 1 house = S(1) = money value of house 1 = H1 * Solution for 2 houses = S(2) = max(H2, S(1)) * S(3) = max(H3 + S(1), S(2)) * ... * S(n) = max(Hn + S(n - 2), S(n - 1)) * * @author Chip Killmar */ public class Houses { public static void main(String[] args) throws Exception { // Create some houses with random money values. Random random = new Random(); House[] houses = new House; for (int i = 0; i < houses.length; ++i) { House house = new House(String.valueOf(i), random.nextInt(4)); houses[i] = house; } System.out.println("Input=" + Arrays.toString(houses)); System.out.println("Output=" + chooseHouses(Arrays.asList(houses))); } /** * An O(n) algorithm that chooses the houses such that the total money value of the houses is maximized, with the * constraint that no two houses chosen can be adjacent to each other. * * @param houses An array of input houses. * @return The result as a 2-tuple of {Total Money, List of Houses}. */ private static Tuple2> chooseHouses(List houses) { List>> results = new ArrayList>>(houses.size()); for (int i = 0; i < houses.size(); ++i) { if (i == 0) { int money = houses.get(0).getMoney(); List housesResult = new ArrayList(); housesResult.add(houses.get(0)); Tuple2> result = new Tuple2>(money, housesResult); results.add(result); } else if (i == 1) { int money = houses.get(1).getMoney() > houses.get(0).getMoney() ? houses.get(1).getMoney() : houses.get(0).getMoney(); List housesResult = new ArrayList(); housesResult.add(houses.get(1).getMoney() > houses.get(0).getMoney() ? houses.get(1) : houses.get(0)); Tuple2> result = new Tuple2>(money, housesResult); results.add(result); } else { Tuple2> previousPreviousResult = results.get(i - 2); Tuple2> previousResult = results.get(i - 1); int previousMoney = previousResult.getFirst(); int currentMoney = previousPreviousResult.getFirst() + houses.get(i).getMoney(); Tuple2> result; if (currentMoney > previousMoney) { List housesResult = new ArrayList(previousPreviousResult.getSecond()); housesResult.add(houses.get(i)); result = new Tuple2>(currentMoney, housesResult); } else { result = new Tuple2>(previousMoney, previousResult.getSecond()); } results.add(result); } } return results.get(results.size() - 1); } private static class House { private String name; private int money; public House(String name, int money) { this.name = name; this.money = money; } public String getName() { return name; } public int getMoney() { return money; } @Override public String toString() { final StringBuilder sb = new StringBuilder(); sb.append("House"); sb.append("{name='").append(name).append('\''); sb.append(", value=").append(money); sb.append('}'); return sb.toString(); } } private static class Tuple2 { private T first; private U second; public Tuple2(T first, U second) { if (first == null) { throw new NullPointerException("first"); } if (second == null) { throw new NullPointerException("second"); } this.first = first; this.second = second; } public T getFirst() { return first; } public U getSecond() { return second; } @Override public String toString() { final StringBuilder sb = new StringBuilder(); sb.append("Tuple2"); sb.append("{first=").append(first); sb.append(", second=").append(second); sb.append('}'); return sb.toString(); } } }