Mercurial > hg > problem6

comparison optim.py @ 13:ad39a394a011 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
12:9f485ecdc2a9 13:ad39a394a011
134 maxplan = plan 134 maxplan = plan
135 except InvalidPlan: 135 except InvalidPlan:
136 pass 136 pass
137 137
138 return maxcapital 138 return maxcapital
139
140 def greedy(case):
141 """Greedy algorithm, considering each machine only once, in decreasing
142 order of maxprofit.
143
144 """
145 machines = sorted(case.machines, key = lambda m: -m.maxprofit)
146 N = len(machines)
147 maxcapital = case.capital
148
149 # Base plan, pick no machine
150 plan = [False]*len(machines)
151 maxplan = plan
152
153 for idx in range(0, N):
154 plan[idx] = True
155 try:
156 plancapital = final_capital(case, machines, plan)
157 if plancapital > maxcapital:
158 maxcapital = plancapital
159 maxplan = plan
160 else:
161 plan[idx] = False
162 except InvalidPlan:
163 plan[idx] = False
164
165 return maxcapital, maxplan
166
139 def main(): 167 def main():
140 cases = parseinput("input.txt") 168 cases = parseinput("input.txt")
141 for (number, case) in enumerate(cases): 169 for (number, case) in enumerate(cases):
142 maxcapital = brute_force(case) 170 maxcapital = brute_force(case)
143 print "Case %d: %d" % (number + 1, maxcapital) 171 print "Case %d: %d" % (number + 1, maxcapital)