Hello,
Does anyone have any idea about a solution to PIGBANK in Python? I'm using DP in my algorithms but I get TLE on the judge.
Accepted solutions to PIGBANK in Python:
https://www.spoj.pl/ranks/PIGBANK/lang=PYTH
Thanks
def pigbank(coins, money_weight):
"pull method"
f = [0] +[25000001] * money_weight
for s in range(1, money_weight + 1):
x = [ p + f[s - w] for p,w in coins if w <= s ]
if x:
f[s]=min(x)
if f[-1] > 25000000:
print "This is impossible."
else:
print "The minimum amount of money in the piggy-bank is "+str(f[-1])+"."[/code]
and the second solution:
[code]def pigbank2(coins, money_weight):
"push method"
coins=sort(coins)
g = [0] + [25000001] * money_weight
L = [0]
for s in L:
for coin in coins:
s1 = s + coin[1]
if s1 > money_weight:
break
else:
u = coin[0] + g[s]
if u < g[s1]:
g[s1]=u
L.append(s1)
if g[-1] > 25000000:
print "This is impossible."
else:
print "The minimum amount of money in the piggy-bank is "+str(g[-1])+"."
def sort(coins):
coins=[[w,p] for p,w in coins]
coins.sort()
return [[p,w] for w,p in coins]
Both work but get TLE on judge...