Table of Contents
Introduction
The task is to find the number of ways we can make the change of given N cents having infinite supply of Coins = { C1, C2,C3 …. Cn} valued coins.
Program
Approach 1
def sol(array, length, Ncents): result_table = [[0 for count in range(length)] for count in range(Ncents+1)] for x in range(length): result_table[0][x] = 1 # Fill table in bottom up manner for x in range(1, Ncents+1): for y in range(length): #Do not contain lth coin count = result_table[x - array[y]][y] if x-array[y] >= 0 else 0 #Contain lth coin count1 = result_table[x][y-1] if y >= 1 else 0 result_table[x][y] = count + count1 return result_table[Ncents][length-1] ip_array = [1, 2, 5, 10] Ncents = int(input("Enter the value: ")) print("The number of solutions are: ",sol(ip_array, len(ip_array) , Ncents))
Output:
Approach 2
def sol(arr,length, N): result_table = [0 for k in range(N+1)] result_table[0] = 1 # Update table if index >= value of picked coin for x in range(0,length): for y in range(arr[x],N+1): result_table[y] += result_table[y-arr[x]] return result_table[N] ip_array = [1, 2, 5, 10] Ncents = int(input("Enter the value: ")) print("The number of solutions are: ",sol(ip_array, len(ip_array) , Ncents))
Output
Explanation
There can be two sub-problems to the given problem:
- Solution containing nth coin
- Solution do not contacting nth coin.
The total count can be obtained by adding both the solutions.
0 Comments