Dynamic Change-Making Algorithm Implementation

Name : Lathiya Dhruvil                                        Enrollment No. : 200420107127     Date : 18/11/22      Subject : Analysis and Design of Algorithm     Subject code : 3150703   2022-23/BE_III_CO_DIV-II/Sem-                           Computer Engg. Deptt., SCET, Surat 5/ADA   Practical No. : 10  Problem Statement:    Implementation of making change algorithm using  dynamic strategy.   Input:  Code:  INF = 100000  def min(x, y):   if x < y:     return x   return y  def coin_change(d, n, k):   M = [0]*(n+1)    for j in range(1, n+1):     minimum = INF      for i in range(0, k):       if(j >= d[i]):         minimum = min(minimum, 1+M[j-d[i]])     M[j] = minimum   return M[n]  d = [] n = int(input("Enter number of elements : ")) print("Enter the values of coins : ")  for i in range(0, n):     a= int(input())     d.append(a)         print(d) k=len(d) print("The least number of coins whose sum is equal to required sum is : ") print(coin_change(d, 7, k))    Output:    

Name : Lathiya Dhruvil                                        Enrollment No. : 200420107127     Date : 18/11/22      Subject : Analysis and Design of Algorithm     Subject code : 3150703   2022-23/BE_III_CO_DIV-II/Sem-                           Computer Engg. Deptt., SCET, Surat 5/ADA