Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
memoized branch and bound solution in Speedy category for Making Change by gyahun_dash
from fractions import gcd
from itertools import accumulate
from math import ceil
def checkio(price, denoms):
ascent = sorted(denoms)
gcds = list(accumulate(ascent, gcd))
supremum = 1 + ceil(price / ascent[0])
def memoize(bb):
results = {}
def _memoize(*args):
if args in results: return results[args]
result = results[args] = bb(*args)
return result
return _memoize
@memoize
def branch_and_bound(price, index, subsum=0):
denom = ascent[index]
if price % gcds[index]: return None
quo, rem = divmod(price, denom)
if not rem: return subsum + quo
nonlocal supremum
offset = rem < ascent[0]
small = ascent[index - 1]
thresh = (price + subsum * denom - supremum * small) / (denom - small)
subs = range(subsum + quo - offset, max(subsum, ceil(thresh)) - 1, -1)
rests = range(rem + offset * denom, price + 1, denom)
minimum = None
for rest, sub in zip(rests, subs):
if ceil(rest / small) + sub < supremum:
branch = branch_and_bound(rest, index - 1, sub)
if branch: minimum = supremum = min(branch, supremum)
return minimum
return branch_and_bound(price, len(ascent) - 1)
April 1, 2016
Comments:
