USACO Money Systems, Dynamic Programming (Python)

USACO Money Systems¶

Problem Statement¶

http://sites.google.com/site/codetrick/moneysystems

Tushar Roy video on this version of the Change Problem:¶

http://www.youtube.com/watch?v=_fgjrs570YE

In [1]:

# SAMPLE INPUT
# 
# 3 10
# 1 2 5

In [2]:

fin = open('money.in', 'r')
fout = open('money.out', 'w')
coins = []
V,N  = map(int, fin.readline().split())
print(V,N)
while len(coins) < V:
    line = fin.readline().strip()
    coins += [int(x.strip()) for x in line.split()]
print(coins)    

3 10
[1, 2, 5]

In [3]:

# Label Columns 0 to N
# Lablel Rows 0 to V
F = [[0]*(N+1) for _ in range(V+1)]
F[0][0] = 1

In [4]:

# Outside loop rows
for v in range(1,V+1):
    coin = coins[v-1]
    
    # F(v,n)=F(v-1,n)+F(v,n-coin)
    # inside loop columns
    for n in range(N+1):
        F[v][n] += F[v-1][n]
        if n >= coin:
            F[v][n] += F[v][n-coin]
            
for row in F:
    print(row)            

[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
[1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10]

In [5]:

print(F[V][N])
fout.write(str(F[V][N]) + "\n")        
fout.close()

10