Mercurial > hg > problem6
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):