RP Zero

RP Zero

anything = [260, 292, 390, 395, 440, 487, 520, 585, 750, 790, 880, 975, 1350, 1820, 3250]
skins = [195,260,390,487,520,675,750,975,1350,1820,3250]
rp20 = [0, 650, 1300, 1950, 2600, 1380, 2030, 2680, 2760, 2800]

def printPurchase(v,ans):
    ret = []
    for i in xrange(len(v)):
        if(ans[i]!=0):
            ret.append(str(ans[i])+' '+str(v[i])+('s' if ans[i]>1 else ''))
    return ret
            

def doIt(v, c, money):
    temp = 0
    for i in xrange(len(money)):
        temp = combi(v, c + money[i])
        if temp!= float('inf'):
            print printPurchase(v,temp)
            print money[i]

def combi(v, c):
    cur = minChange(v,c)
    
    if cur == float('inf'):
        return float('inf')
    
    com = 0
    ret = [0] * len(v)
    
    while c != 0:
        for i in xrange(len(ret)):
            com = minChange(v, (c - v[i]))
            if (com!='inf' and cur == com + 1):
                c -= v[i]
                cur = com
                ret[i]+=1
                break
    return ret

       
def minChange(v, c):
    m, n = len(v)+1, c+1
    table = [[0] * n for x in xrange(m)]
    for j in xrange(1, n):
        table[0][j] = float('inf')
    for i in xrange(1, m):
        for j in xrange(1, n):
            aC = table[i][j - v[i-1]] if j - v[i-1] >= 0 else float('inf')
            table[i][j] = min(table[i-1][j], 1 + aC)
    return table[m-1][n-1]

##########################################################################

print 'Enter your RP and I\'ll list how you can zero out for less than 20 dollars'
x = int(raw_input())
doIt(skins, x, rp20)
pause = raw_input("Press any button to exit")