crististm
Jun '07

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=PYTH47

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...