County Money in Greedy Algorithm

Given a value V, if we want to make a change for V Rs, and we have an infinite supply of each of the denominations in Indian currency, i.e., we have an infinite supply of { 1, 2, 5, 10, 20, 50, 100, 500, 1000} valued coins/notes, what is the minimum number of coins and/or notes needed to make the change?

Examples:

Input: V = 70
Output: 2
We need a 50 Rs note and a 20 Rs note.

Input: V = 121
Output: 3
We need a 100 Rs note, a 20 Rs note and a 1 Rs coin. 

Solution: Greedy Approach.

Approach: A common intuition would be to take coins with greater value first. This can reduce the total number of coins needed. Start from the largest possible denomination and keep adding denominations while the remaining value is greater than 0.

Algorithm:

1. Sort the array of coins in decreasing order.

2. Initialize result as empty.

3. Find the largest denomination that is smaller than current amount.

4. Add found denomination to result. Subtract value of found denomination from amount.

5. If amount becomes 0, then print result.

6. Else repeat steps 3 and 4 for new value of V.

Example in C++

// C++ program to find minimum 
// number of denominations 
#include <bits/stdc++.h> 
using namespace std; 
  
// All denominations of Indian Currency 
int deno[] = { 1, 2, 5, 10, 20, 
 50, 100, 500, 1000 }; 
int n = sizeof(deno) / sizeof(deno[0]); 
  
void findMin(int V) 
{ 
 sort(deno, deno + n); 
  
 // Initialize result 
 vector<int> ans; 
  
 // Traverse through all denomination 
 for (int i = n - 1; i >= 0; i--) { 
  
 // Find denominations 
 while (V >= deno[i]) { 
 V -= deno[i]; 
 ans.push_back(deno[i]); 
 } 
 } 
  
 // Print result 
 for (int i = 0; i < ans.size(); i++) 
 cout << ans[i] << " "; 
} 
  
// Driver program 
int main() 
{ 
 int n = 93; 
 cout << "Following is minimal"
 << " number of change for " << n 
 << ": "; 
 findMin(n); 
 return 0; 
} 

Output:

Following is minimal number of change 
for 93: 50  20  20  2  1

C

// C program to find minimum 
// number of denominations 
#include <stdio.h> 
#define COINS 9 
#define MAX 20 
  
// All denominations of Indian Currency 
int coins[COINS] = { 1, 2, 5, 10, 20, 
 50, 100, 200, 2000 }; 
  
void findMin(int cost) 
{ 
 int coinList[MAX] = { 0 }; 
 int i, k = 0; 
  
 for (i = COINS - 1; i >= 0; i--) { 
 while (cost >= coins[i]) { 
 cost -= coins[i]; 
 // Add coin in the list 
 coinList[k++] = coins[i]; 
 } 
 } 
  
 for (i = 0; i < k; i++) { 
 // Print 
 printf("%d ", coinList[i]); 
 } 
 return; 
} 
  
int main(void) 
{ 
 // input value 
 int n = 93; 
  
 printf("Following is minimal number"
 "of change for %d: ", 
 n); 
 findMin(n); 
 return 0; 
} 
// Code by Munish Bhardwaj 

Output:

Following is minimal number of change 
for 93: 50  20  20  2  1

Python

# Python 3 program to find minimum  
# number of denominations 
  
def findMin(V): 
  
 # All denominations of Indian Currency 
 deno = [1, 2, 5, 10, 20, 50,  
 100, 500, 1000] 
 n = len(deno) 
  
 # Initialize Result 
 ans = [] 
  
 # Traverse through all denomination 
 i = n - 1
 while(i >= 0): 
  
 # Find denominations 
 while (V >= deno[i]): 
 V -= deno[i] 
 ans.append(deno[i]) 
  
 i -= 1
  
 # Print result 
 for i in range(len(ans)): 
 print(ans[i], end = " ") 
  
# Driver Code 
if __name__ == '__main__': 
 n = 93
 print("Following is minimal number", 
 "of change for", n, ": ", end = "") 
 findMin(n) 
  
# This code is contributed by 
# Surendra_Gangwar 

Output:

Following is minimal number of change 
for 93: 50  20  20  2  1

Java

// Java program to find minimum 
// number of denominations 
import java.util.Vector; 
  
class GFG  
{ 
  
 // All denominations of Indian Currency  
 static int deno[] = {1, 2, 5, 10, 20,  
 50, 100, 500, 1000}; 
 static int n = deno.length; 
  
 static void findMin(int V) 
 { 
 // Initialize result  
 Vector<Integer> ans = new Vector<>(); 
  
 // Traverse through all denomination  
 for (int i = n - 1; i >= 0; i--) 
 { 
 // Find denominations  
 while (V >= deno[i])  
 { 
 V -= deno[i]; 
 ans.add(deno[i]); 
 } 
 } 
  
 // Print result  
 for (int i = 0; i < ans.size(); i++) 
 { 
 System.out.print( 
 " " + ans.elementAt(i)); 
 } 
 } 
  
 // Driver code  
 public static void main(String[] args)  
 { 
 int n = 93; 
 System.out.print( 
 "Following is minimal number "
 +"of change for " + n + ": "); 
 findMin(n); 
 } 
} 
  
// This code is contributed by 29AjayKumar 

Output:

Following is minimal number of change 
for 93: 50  20  20  2  1

Source: geeksforgeeks