changeset 13:ad39a394a011 draft

greedy: new greedy algorithm, works reasonably well
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Wed, 11 Mar 2015 16:44:55 -0400
parents 9f485ecdc2a9
children a72cf3c7c976
files optim.py
diffstat 1 files changed, 28 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- 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):