# HG changeset patch
# User Jordi Gutiérrez Hermoso <jordigh@octave.org>
# Date 1426106695 14400
# Node ID ad39a394a011191977291710db9df0d37ae05547
# Parent  9f485ecdc2a920e75c820c3438ce98a95f02d892
greedy: new greedy algorithm, works reasonably well

diff --git a/optim.py b/optim.py
--- a/optim.py
+++ b/optim.py
@@ -136,6 +136,34 @@
             pass
 
     return maxcapital
+
+def greedy(case):
+    """Greedy algorithm, considering each machine only once, in decreasing
+    order of maxprofit.
+
+    """
+    machines = sorted(case.machines, key = lambda m: -m.maxprofit)
+    N = len(machines)
+    maxcapital = case.capital
+
+    # Base plan, pick no machine
+    plan = [False]*len(machines)
+    maxplan = plan
+
+    for idx in range(0, N):
+        plan[idx] = True
+        try:
+            plancapital = final_capital(case, machines, plan)
+            if plancapital > maxcapital:
+                maxcapital = plancapital
+                maxplan = plan
+            else:
+                plan[idx] = False
+        except InvalidPlan:
+            plan[idx] = False
+
+    return maxcapital, maxplan
+
 def main():
     cases = parseinput("input.txt")
     for (number, case) in enumerate(cases):