1 files changed, 81 insertions, 0 deletions
diff --git a/picker.java b/picker.java
new file mode 100644
index 0000000..708273c
--- /dev/null
+++ b/picker.java
@@ -0,0 +1,81 @@
+import java.util.*;
+import java.io.*;
+
+public class Stock {
+    int price, value;
+    String ticker;
+
+    public Stock() {
+		price = 0;
+		value = 0;
+		ticker = "";
+    }
+
+    public Stock(int price, int value, String ticker) {
+		this.price = price;
+		this.value = value;
+		this.ticker = ticker;
+    }
+}
+
+public class Backpointer {
+    static Stock NOTHING = new Stock(1, 0, "");
+
+    int previousValue, totalValue;
+    Stock stock;
+
+    public Backpointer(int previousValue, Stock stock) {
+		this.stock = stock;
+		this.totalValue = previousValue + stock.value;
+    }
+
+	public static Backpointer chooseBackpointer(Stock stocks[],
+		ArrayList<Backpointer> backpointers) {
+
+		int currentPrice = backpointers.size();
+		Backpointer best = 
+		new Backpointer(backpointers.get(currentPrice - 1).totalValue, NOTHING);
+		for (int i = 0; i < stocks.length; i++) {
+    		Stock stock = stocks[i];	
+	    	int previousPrice = currentPrice - stock.price;
+	    	if (previousPrice >= 0) {
+	    		Backpointer candidate = 
+	    		new Backpointer(backpointers.get(previousPrice).totalValue, stock);
+			    if (candidate.totalValue > best.totalValue) {
+	    	    	best = candidate;
+			    }
+		    }
+		}
+		return best;
+	}
+
+	public static ArrayList chooseStocks(Stock stocks[], int priceLimit) {
+		// assert stock values are integers
+		
+		// create backpointers
+		ArrayList<Backpointer> backpointers = new ArrayList<Backpointer>();
+		backpointers.add(new Backpointer(0, NOTHING));
+		while (backpointers.size() <= priceLimit) {
+			backpointers.add(chooseBackpointer(stocks, backpointers));
+		}
+
+		// postprocess backpointers
+		ArrayList<Stock> result = new ArrayList<Stock>();
+		for (int price = priceLimit; price > 0; 
+		price -= backpointers.get(price).stock.price) {
+			Stock stock = backpointers.get(price).stock;
+			if (stock != NOTHING)
+				result.add(stock);
+			result.add(backpointers.get(price).stock);
+		}
+		Collections.reverse(result);
+
+		return result;
+	}
+
+	public static void main(String[] args) {
+		Stock stocks[] = {new Stock(3, 10, "A"), new Stock(4, 14, "B")};
+		int priceLimit = 10;
+		ArrayList result = chooseStocks(stocks, priceLimit);
+	}
+}