Python program to implement Coin Change Problem using Greedy Approach

# COIN CHANGE PROBLEM using GREEDY METHOD

class Coin:
    value=0
    number=0
 
A=[]
amount=0
n=0 # n is the Number of coins

def getData():
    global A
    global amount
    global n

    amount=int(input("Enter Amount: "))
    n=int(input("Enter type of different coins: "))
    
    for i in range(n): 
        A.append(Coin())
        A[i].value=int(input("\n\tEnter value_of_coin "))


def showData():
    global A
    global amount
    global n
    
    print("\n*** Inputs ***\n")

    print("\nAmount: ",amount)
    print("\nValue of coin")
    print("\n-------------")
    for i in range(n):  
        print("\n\t",A[i].value)


def bSort(): # Using Bubble sort
    global A
    global amount
    global n

    flag = 1
    for i in range(0,n-1):  
        if flag==1:
            for j in range(0,n-1):
                if A[j].value < A[j+1].value:
                    temp=[]
                    temp.append(Coin())
                    temp = A[j]
                    A[j] = A[j+1]
                    A[j+1] = temp
                    flag = 1    


def output():
    global A
    global amount
    global n
    
    # Displaying optimal solution
    print("Optimal solution of the coins <",A[0].value,end="")
    for i in range(1,n):    
        print(", ",A[i].value,end="")   # end="" is used to remove default newline

    print("> is <",A[0].number,end="")
    
    for i in range(1,n):    
        print(", ",A[i].number,end="")
    
    print(">\n\n")


def solution():
    global A
    global amount
    global n
    
    bSort()
    print("\n\n*** Outputs ***")
    print("\n\nOptimal Solution")
    print("\n----------------")
    sum = 0
    rAmount = amount
    for i in range(n):  
        A[i].number = rAmount // A[i].value     # '//' returns integer value after division
        addAmount = A[i].number * A[i].value
        sum += addAmount
        rAmount -= addAmount
        print("\n",A[i].value," * ",A[i].number,"= ",addAmount)
    
    print("\n_____________")
    print("\nSum= ",sum,"\n")
    output()


# __________________________ Main Block Starts __________________________
print("\t\t\t____COIN CHANGE PROBLEM using GREEDY METHOD____")
getData()
showData()
solution()

Output