project2.py

from time import clock
from random import randint
import sys

def changeslow(V, A):
    C = [0]*len(V)
    minimum = changeslowhelper(V, A, C)
    return (minimum[0], minimum[1])

def changeslowhelper(V, A, C):
    if A == 0:
        D = C[:]
        return (0, D)
    elif A > 1:
        minimum = None
        current = None
        kept = 0
        for i in range(0, len(V)):
            current = changeslowhelper(V, A-V[i], C)
            if minimum == None or current[0] < minimum[0]:
                minimum = current
                kept = i
        minimum[1][kept]+= 1
        return (minimum[0]+1, minimum[1])
    else:
        D = C[:]
        return (float("inf"), D)

def changegreedy(V, A):
    C = [0]*len(V)
    i = len(V) - 1
    K = A
    num_coins = 0
    while K > 0:
        if V[i] <= K:
            K -= V[i]
            C[i] += 1
            num_coins += 1
        else:
            i-=1
    return num_coins, C

def changedp(V, A):
	C = [0]*len(V)
	T = [None] * (A+1)
	#for i in range(0, A+1):
	#    T[1][i] = None
	minimum = changedphelper(V, A, T, C)
	return (minimum[0], minimum[1])

def changedphelper(V, A, T, C):
    if A < 0:
        D = C[:]
        return (float("inf"), D)
    elif T[A] != None:
        return (T[A][0],T[A][1][:])
    elif A == 0:
        D = C[:]
        return (0, D)
    elif A > 0:
        minimum = None
        kept = 0
        current = None
        for i in range(0, len(V)):
            current = changedphelper(V, A-V[i], T, C)
            if minimum == None or (current[0] < minimum[0]):
                minimum = current
                kept = i
        minimum[1][kept] += 1
        D = minimum[1][:]
        T[A] = (minimum[0]+1, D)
        return (minimum[0]+1, minimum[1])