Algoritmo codicioso para encontrar el número mínimo de monedas

Dado un valor V, si queremos hacer un cambio por V Rs, y tenemos una oferta infinita de cada una de las denominaciones en moneda india, es decir, tenemos una oferta infinita de { 1, 2, 5, 10, 20, 50, 100, 500, 1000} monedas/billetes valorados, ¿cuál es el número mínimo de monedas y/o billetes necesarios para hacer el cambio?

Ejemplos:  

// 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;
}

// 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

// 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

# Python3 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

// C# program to find minimum
// number of denominations
using System;
using System.Collections.Generic;
  
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 
    List<int> ans = new List<int>();
  
    // 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.Count; i++)
    {
        Console.Write(" " + ans[i]);
    }
}
  
// Driver code 
public static void Main(String[] args) 
{
    int n = 93;
    Console.Write("Following is minimal number " +
                  "of change for " + n + ": ");
                    
    findMin(n);
}
}
  
// This code is contributed by gauravrajput1

<script>
// Javascript program to find minimum
// number of denominations
  
// All denominations of Indian Currency
let deno=[1, 2, 5, 10, 20,
    50, 100, 500, 1000];
let n = deno.length;
  
function findMin(V)
{
    // Initialize result
        let ans = [];
   
        // Traverse through all denomination
        for (let i = n - 1; i >= 0; i--)
        {
            // Find denominations
            while (V >= deno[i])
            {
                V -= deno[i];
                ans.push(deno[i]);
            }
        }
   
        // Print result
        for (let i = 0; i < ans.length; i++)
        {
            document.write(
                " " + ans[i]);
        }
}
  
// Driver code
n = 93;
document.write(
"Following is minimal number "
+"of change for " + n + ": ");
findMin(n);
  
  
// This code is contributed by rag2127
</script>