Ejercio de programación greedy: main code

No comprendí la lógica de este algoritmo.
Alguien tan amable que me lo pueda explicar

No recursivo, pero es codicioso.
Made in C++:

#include <iostream>
#include <stack>
#include <vector>

int main() 
{
  std::stack<int> usadas;
  std::vector<int> lista;
  lista={1,5,10,15,20};
  int tam = lista.size();
  int cambio = 94;
  std::cout << "Para dar cambio de $" << cambio << " se necesitan:\n";
  for(int i = tam-1; i >= 0; i--)
  {
    while(cambio >= lista[i])
    {
      cambio = cambio - lista[i];
      usadas.push(lista[i]);
    }
  }
  while (!usadas.empty())
  {
    std::cout << "\nMoneda de: $" << usadas.top();
    usadas.pop();
  }
}

Ver funcionamiento.

Dar un cambio Exacto Algoritmo Voraz con Elixir

• Se puede ingresar cualquier valor
• Uso de recursividad
• Algoritmo Voraz

defmodule CambioMoneda do
  def get_cambio(0, denominacion), do: denominacion
  def get_cambio(cambio, denominacion) do
    [valor, _] = moneda_usar = val_monedas(cambio, denominacion)
    ind = Enum.find_index(denominacion, fn([x,_]) -> x == valor end)
    denominacion = List.replace_at(denominacion, ind, moneda_usar)
    get_cambio(val_cambio(cambio, denominacion), denominacion)
  end

  def val_monedas(0, x), do: x
  def val_monedas(_, []), do: []
  def val_monedas(x, [[val, retorno] | _]) when x >= val, do: [val, retorno + 1]
  def val_monedas(x, [_ | tail]), do: val_monedas(x, tail)

  def val_cambio(0, _), do: 0
  def val_cambio(x, []), do: x
  def val_cambio(x, [[val, _] | _]) when x >= val, do: x - val
  def val_cambio(x, [_ | tail]), do: val_cambio(x, tail)
end

defmodule Ejecucion do
  def imprimirCambio([]), do: IO.puts("")
  def imprimirCambio([[x, y] | tail]) do
    IO.puts("La cantidad de monedas de #{x} es: #{y}")
    imprimirCambio(tail)
  end
  # Recursivamente imprime

  def main do
    IEx.configure(inspect: [charlists: :as_lists])

    IO.puts("Dar cambio con la menor cantidad de monedas")
    IO.puts("----")
    denominacion = [ [20, 0], [15, 0], [10, 0], [5, 0], [1, 0] ]
    {cambio, _} = Integer.parse(IO.gets("Ingrese el valor a generar cambio: "))
    denominacion = CambioMoneda.get_cambio(cambio, denominacion)
    IO.puts("---- Cambio a entregar ----")
    imprimirCambio(denominacion)
    :ok
  end
end

Ejecución

1. Se Carga iex
2. Se ejecuta

Ejecucion.main()

1. Se obtienen resultados similares a:

Mi algoritmo greedy en Javascript

function greedyCoins(deuda,i,billete,nb){
  if (deuda == 0){
    console.log ("pago completado");
    return 0
    }
  else{
    //mira si la deuda se puede pagar con el billete que se está viendo
    var pagoDisp = parseInt(deuda/billete[i]);
    if (pagoDisp > 0){
      //se paga la deuda
      var pagoRealizado = billete[i] * pagoDisp;
      //se entregan los billetes
      console.log(pagoRealizado);
      //se resta la cantidad entregada de la deuda
      deuda-=pagoRealizado;
    }
  }
  if (i<nb){
    i+=1;
    //recursividad:
    greedyCoins(deuda,i,billete,nb);
  }
  else{
    console.log("pago completado");
  }
}

let billete = [50,20,10,5,2,1];
var nb = 6;
var i = 0;
var deuda = 138;

greedyCoins(deuda,i,billete,nb)

Lo dejo hecho en Python3

import random

def greedy_change(coins_set, change, coins):

    for i in range(len(coins_set)):
        if change == 0:
            
            return coins
        
        if change < max(coins_set) and len(coins_set) > 1:
            coins_set.remove(max(coins_set))
        
        if change >= max(coins_set):
            coins.append(max(coins_set))
            return greedy_change(coins_set, change - max(coins_set), coins)


if __name__ == '__main__':

    change = random.randint(7, 100)
    print(f'Se devolveran {change} pesos de vuelto\n')
    coins_set = [1, 5 ,10, 20]
    coins = []

    greedy_change(coins_set, change, coins)
    print('Entregaremos las siguientes monedas: ', coins)

Hola, Me ha dado un poco de dolor de cabeza entender el código del profesor, después que lo logre entender, me dí cuenta que consume muchos recursos cuando le colocamos un N=100 porque las interacciones que tiene que realizar son muchísimas es casi N^2, por eso realice un código con referencia al que profesor realizó, pero mas eficiente.

Mi solución es la Siguiente:

#include <stdio.h>
#include <stdlib.h>
int cantidad_moneda;
int moneda_20;
int moneda_15;
int moneda_10;
int moneda_5;
int moneda_1;

int Greedy_CoinChange(int coins[], int n ,int N) {
 int i=n-1;
 if(N==0)
 {
   return 0; // indicar que no hay valores de moneda para 0
 }

 if  (N<0)
 {
   return -2; //indicar valor incorrecto
 }

  while(N!=0) {
    if(coins[i] > N) {
      i--;
    }
    else {
      switch(coins[i])
      {
        case 20: moneda_20++;
        break;
        case 15: moneda_15++;
        break;
        case 10: moneda_10++;
        break;
        case 5: moneda_5++;
        break;
        case 1: moneda_1++;
        break;
      }
      printf("%d\t",coins[i]); // imprime la moneda que va a elegir 
      cantidad_moneda++;          // cuantificar la cantidad de moneda a devolver
      N = N-coins[i];
    }
  }
  printf("\n");
  
}

int main(int argc, char const *argv[])
{
    int coins[]={1,5,10,15,20};
    int n = sizeof(coins)/sizeof(coins[0]);
    int N = 27;

   Greedy_CoinChange(coins,n,N);

 printf("Cantidad total de Moneda a Devolver -> %d:\n",cantidad_moneda);
 printf("Cantidad total de Moneda de %d es: %d\t\n",coins[0],moneda_1);
 printf("Cantidad total de Moneda de %d es: %d\t\n",coins[1],moneda_5);
  printf("Cantidad total de Moneda de %d es: %d\t\n",coins[2],moneda_10);
   printf("Cantidad total de Moneda de %d es: %d\t\n",coins[3],moneda_15);
    printf("Cantidad total de Moneda de %d es: %d\t\n",coins[4],moneda_20);


    return 0;
}

Prueba Para N=27

Cantidad total de Moneda a Devolver -> 4:
Cantidad total de Moneda de 1 es: 2     
Cantidad total de Moneda de 5 es: 1
Cantidad total de Moneda de 10 es: 0
Cantidad total de Moneda de 15 es: 0
Cantidad total de Moneda de 20 es: 1

Prueba para N=233

Cantidad total de Moneda a Devolver -> 15:
Cantidad total de Moneda de 1 es: 3
Cantidad total de Moneda de 5 es: 0
Cantidad total de Moneda de 10 es: 1
Cantidad total de Moneda de 15 es: 0
Cantidad total de Moneda de 20 es: 11

INT_MAX

Representa el valor Maximo que puede tener un numero entero almacenado en 32 bits
Pertenece a la biblioteca climits (en c++), limits.h (en c)

El numero es interesante

Esta clase se podría catalogar como algoritmo greedy. El objetivo es dar de un cajero, la cantidad minima de billetes

"""Algoritmo Greedy, busca el mínimo de billetas para dar en un cajero"""

class Cajero:
   
    def __init__(self):
        self.cajero = [50,20,10,5]
        self.billetes = [0,0,0,0]
        self.cambio = [0,0,0,0]
        self.total = 0
    
    def cargaCajero(self):
        """Ingresar dinero en el cajero"""
    
        for i in range(4):
            self.billetes[i] = int(input("Introduce billetes de {}:".format(self.cajero[i])))
        
    
    def imprimeBilletes(self):
        """Nos dice los billetes que hay en el cajero""" 
        total = 0
        for i in range(4):
            print("Billetes de {}: {}".format(self.cajero[i], self.billetes[i]))
            total += self.cajero[i] * self.billetes[i]
        return total
    
    def sacar(self, cant):
        """Saca la cantidad mínima de billetes del cajero"""
        for i in range(4):
            if self.billetes[i] > 0:
                self.cambio[i] = cant // self.cajero[i]
                cant = cant - (self.cambio[i] * self.cajero[i])
                self.billetes[i] -= self.cambio[i]                                
        return self.cambio
    
       
if __name__ == "__main__":
    billetes = 0
    cajero = Cajero()
    cajero.cargaCajero()
    total = cajero.imprimeBilletes()
    cantidad = int(input("Dinero a sacar del cajero: "))
    if cantidad > total:
        print("No se puede sacar {}€, el cajero no dispone de cantidad suficiente")
    else:
        billetes = cajero.sacar(cantidad)
        print(billetes)
    total = cajero.imprimeBilletes()
    print("Queda en cajero {}€ ".format(total))

Les dejo la implementación del algoritmo en JS devolviendo que monedas se usaron en vez del número, son 3:
1.-Tiene que estar ordenado de Mayor a Menor (si no basta con agregar un sort al coinSet en la primer llamada).
2.- No requiere ordenación pero es más tardado.
3 No requiere ordenación y sirve para hacerlo con un inventario de monedas, es decir un array de todas las monedas y sus denominaciones posibles.

function greedyChange(coinSet, change, res) {
    if (change <= 0) {
        return res;
    }
    for (let i = 0; i < coinSet.length; i++) {
        if (change - coinSet[i] >= 0) {
            return greedyChange(
                coinSet, 
                change - coinSet[i], 
                res.concat(coinSet[i])); 
        } 
    }
}

function greedyChangeMax(coinSet, change, res) {
    if (change <= 0) {
        return res;
    }
    let temps = []
    for (let i = 0; i < coinSet.length; i++) {
        if (change - coinSet[i] >= 0) {
            temps.push(coinSet[i]);
        } 
    }
    const max = Math.max(...temps);
    return greedyChangeMax(
        coinSet, 
        change - max, 
        res.concat(max)); 
}

function greedyChangeMaxSplice(coinSet, change, res) {
    if (change <= 0) {
        return res;
    }
    let temps = []
    for (let i = 0; i < coinSet.length; i++) {
        if (change - coinSet[i] >= 0) {
            temps.push(coinSet[i]);
        } 
    }
    if (temps.length) {
        const pos = coinSet.lastIndexOf(Math.max(...temps));
        const val = coinSet[pos];
        coinSet.splice(pos, pos);
        return greedyChangeMaxSplice(
            coinSet, 
            change - val, 
            res.concat(val)); 
    } else {
        return res;
    }
}

console.log(greedyChange([20, 15, 10, 5, 1], 27, []));
console.log(greedyChangeMax([15, 20, 5, 10, 1], 27, []));
console.log(greedyChangeMaxSplice([15, 20, 5, 10, 1], 27, []));

Por si quieren ver una solución sencilla en Python, pero sin recursividad.

Implemente el mismo algoritmo que el profesor pero en lenguaje Python. Agregue una lista para capturar los valores de las monedas, adicional al conteo minimo de monedas. Lo que me permitió observar que definitivamente este algoritmo recursivo sería muy ineficiente, puesto que la lista de monedas a probar se expande muchísimo y sólo tenemos 5 opciones.

A continuación les dejo mi código para que analicen.

Pueden tomar como reto, mejorarlo para obtener los valores de las monedas, adicional a la cantidad minima de monedas necesarias para dar el cambio:

def give_change(coins_set, total_coins, total_change, values):
    if total_change == 0:
        return 0
    
    if total_change < 0:
        return -1
    
    coins = -1

    for index in range(total_coins):
        coin = give_change(coins_set, total_coins, total_change - coins_set[index], values)
        if coin != -1:
            coins = coin + 1
            values.append(coins_set[index])
    
    return coins


if __name__ == '__main__':
    coins_set = [1,5,10,15,20]
    total_coins = len(coins_set)
    total_change = 27
    values = []

    
    print("The minimum number of coins to give change is:")
    change = give_change(coins_set, total_coins, total_change, values)
    print(change)
    print()

    print("The values of these coins are:")
    print(values)

Les dejo mi implementación de python que es mucho más simple de entender, NO es recursiva y está bastante optimizada.

def greedy_change(coin_set, n):
    solution = []
    suma = 0
    iteration = 1
    while suma < n:
        # La mejor opción greedy será tomar la moneda de más alta denominación
        best_option = max(coin_set)
        # A tu vuelto, sumale la moneda de más alta denominación
        suma += best_option
        # Mientras NO hayas llegado al número que te pidieron
        if suma <= n:
            # Añade la moneda de más alto valor al la lista de vuelto
            solution.append(best_option)
            print(iteration, solution)
            iteration += 1
        # Si te pasaste entonces:
        else:
            # ignora la última suma que hayas hecho
            suma -= best_option
            # Remueve la "best_option" del set de monedas disponibles
            coin_set.remove(best_option)
    return solution


if __name__ == '__main__':
    coins = [5, 2, 1]
    n = 23
    print("your current budget is:", n)
    print("the coins allowed for change are:", coins)
    print("*"*24)
    ans = greedy_change(coins, n)
    print("*" * 24)
    print("Your change is:", ans)

Valor esperado:

your current budget is: 23
the coins allowed for change are: [5, 2, 1]
************************
1 [5]
2 [5, 5]
3 [5, 5, 5]
4 [5, 5, 5, 5]
5 [5, 5, 5, 5, 2]
6 [5, 5, 5, 5, 2, 1]
************************
Your change is: [5, 5, 5, 5, 2, 1]

Me ha dado mucho que hacer esta clase y este algoritmo. Lo mejor es investigar otras fuentes porque acá la explicación no está completa.

Mi código en C++ (agregué una función para imprimir las monedas).

#include <bits/stdc++.h>
using namespace std;

int greedyChange(int coinSet[], int n, int N)
{
    if(N==0)
        return 0;
    
    int res = INT_MAX;

    for (int i=0; i<n; i++)
    {
        if (coinSet[i] <= N)
        {
            int sub_res = greedyChange(coinSet, n, N-coinSet[i]);
            if(sub_res != INT_MAX && sub_res + 1 < res)
            res = sub_res + 1;
        }
    }
    return res;
}


int findCoins(int coinSet[], int n, int N)
{
    vector<int> ans;

    for (int i = n - 1; i >= 0; i--){
        while (N >= coinSet[i]){
            N -= coinSet[i];
            ans.push_back(coinSet[i]);
        }
    }
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << ", ";
}


int main()
{
    int coinSet[] = {1, 5, 10, 15, 20};
    int n = sizeof(coinSet)/sizeof(coinSet[0]);

    int N = 27;
    cout << "El minimo de monedas requerido es: " << greedyChange(coinSet, n, N) <<"\n";
    cout << "damos de cambio las siguiente monedas: ";
    findCoins(coinSet, n, N);
    cout << "\n";
    return 0;
}```

Reto

Después de bastante esfuerzo pude resolver el reto, usando el código provisto. Lo cierto es que tuve que estudiar mas a fondo como resolver el problema y los conceptos de programación funcional para obtener la respuesta.

La cuestión es que cada vez que se sale del método recursivo se obtiene la mejor solución parcial para el monto que le pasamos como argumento.
Esa solución parcial la guardamos en un arreglo y al final para obtener las solución al problema juntamos cada solución de los sub-problemas lo que nos da la respuesta.

Básicamente es aplicar el principio de subestructura optima: “Subestructura óptima, es decir, la solución óptima de un problema incorpora la solución óptima a los subproblemas”.
Recomiendo esta lectura y las anteriores que me ayudaron a entender el asunto https://www.codesdope.com/course/algorithms-coin-change/

using System;
using System.Collections.Generic;
using System.Text;

namespace StructExample
{
    
    class CoinChanger
    {
        int[] minCoinsUsed;
       
        public CoinChanger(int amount)
        {

            int[] coins = { 1, 2, 5, 10, 15, 20 };

            minCoinsUsed = new int[amount+1];
           
            int coinsToUse = GreedyChange(coins, amount);
            
            Console.WriteLine(" la cantidad de monedas usadas es {0}", coinsToUse);
            
            int k = amount;
            int coin;
            Console.WriteLine("Las monedas usadas son: ");
            for (int i = 1; i <= coinsToUse; i++)
            {
                coin = coins[minCoinsUsed[k]];
                k -= coin;
                Console.WriteLine("* Moneda de " + coin);
            }
            if (k !=0)
            {
                throw new Exception("Quedo una cantidad : " + k);
            }
        }

        int GreedyChange(int[] coinArray, int amount)
        {
            if (amount == 0)
            {
                return 0;
            }
            if (amount < 0)
            {
                return Int16.MaxValue;
            }
            int coinsQuantity = Int16.MaxValue;      
            int coin = -1;            
          
            for (int i = 0; i < coinArray.Length; i++)
            {
                
                int temp = GreedyChange(coinArray, amount - coinArray[i]);
                if (temp != Int16.MaxValue)
                {
                    if (coinsQuantity > temp + 1)
                    {
                        coin = i;                                                              
                        coinsQuantity = temp + 1;
                       
                    }
                }                
            }

            minCoinsUsed[amount] = coin;
            return coinsQuantity;
        }
    }
}

la llamada desde el main es solo:

 CoinChanger greedy = new CoinChanger(26);

Código implementado en Java. Tengo duda si por utilizar el comando break se sigue considerando recursivo o Greedy, espero alguien me pueda aclarar la duda. Gracias.

public class Main {

    public static void main(String[] args) {
	// write your code here
        int[] coinSet = {20,10,5,1};
        int N = 214;
        GreedyChange greedyChange = new GreedyChange();
        greedyChange.greedyChange(coinSet,N);
        greedyChange.printChange();
    }
}

import java.util.ArrayList;
import java.util.List;

public class GreedyChange {
    private final List<Integer> coins = new ArrayList<>();

    public void greedyChange(int[] coinSet, int change) {
        if(change<=0){
            return;
        }
        for (int j : coinSet) {
            if (change - j >= 0) {
                coins.add(j);
                change -= j;
                greedyChange(coinSet, change);
                break;
            }
        }
    }

    public void printChange() {
        System.out.println("The change is being distributed in " + coins.size() + " coins in the following" +
                " way: ");
        int sum = 0;
        for (int i = 0; i < coins.size(); i++) {
            if (i == coins.size() - 1) {
                System.out.print( "$" +coins.get(i));
            } else {
                System.out.print("$" + coins.get(i) + " + ");
            }
            sum += coins.get(i);
        }
        System.out.print(" = $" + sum);
    }

}

Aqui esta mi codigo, lo cambie por completo la logica. Considero que no esta tan bien explicado el video. Les recomiendo los cursos de python con David de Programacion Dinamica y Estocastica.

// AMOUNT OF CHANGE RECURSIVE ALGORITHM
// Date: 17 - October - 2020
// Author: Alejandro Andrade Soriano


#include <iostream>
#include <climits>

using namespace std;

int greedyChange(int coinSet[], int arrLen, int toChange, int amountCoins)
{

  int temp = toChange - coinSet[arrLen - 1];

  if (toChange == 0)
  {
    cout << "Finish! No more change to give." << endl;
    cout << "Amount of coins to give: ";
    return amountCoins;
  }

  if (temp < 0)
  {
    arrLen--;
    cout << "Reducing value of coin to $" << coinSet[arrLen - 1] << endl;
    return greedyChange(coinSet, arrLen, toChange, amountCoins);
  }

  toChange = temp;
  cout << "Taking $" << coinSet[arrLen - 1] << " Rest Change $" << toChange << endl;
  return greedyChange(coinSet, arrLen, toChange, ++amountCoins);
}

int main()
{

  int coinSet[] = {1, 5, 10, 15, 20, 50};
  int n = sizeof(coinSet) / sizeof(coinSet[0]);
  int debt = 326;
  cout << "To change $" << debt << endl;
  cout << "Coin Change\n"
       << greedyChange(coinSet, n, debt, 0) << endl;

  return 0;
}

Es recursivo, no codicioso xD.
Lo hice yo ❤️

#include <iostream>
#include <climits>
using namespace std;

int v = 0, q = 0, d = 0, c = 0, u = 0;

int greedyCoinChange(int coinSet[], int debit) {
  if (debit == 0) {
    return 0;
  }

  int res = 0, j = 0, currentValue, minIndex;
  int count[5];

  for (int i = 4; i >= 0; i--) {
    res = debit - coinSet[i];
    while (res >= 0) {
      j++;
      res -= coinSet[i];
    }
    count[i] = j;
    res = debit;
    j = 0;
  }

  for(int i = 0; i < 5; i++) {
    currentValue = count[0];
    if(currentValue >= count[i] && count[i] != 0) {
      currentValue = count[i];
      minIndex = i;
    }
  }


  res = debit - coinSet[minIndex];

  switch (minIndex) {
    case 0:
      u++;
      break;
    case 1:
      c++;
      break;
    case 2:
      d++;
      break;
    case 3:
      q++;
      break;
    case 4:
      v++;
      break;
  }

  greedyCoinChange(coinSet, res);

  return 0;
}

int main() {
  int coinSet[] = {1, 5, 10, 15, 20};
  int debit;

  cout << "Ingrese su pago por favor: " << endl;
  cin >> debit;

  greedyCoinChange(coinSet, debit);

  cout << "Tu cambio/vuelta es de:"<< endl;
  cout << v << " billete(s) de veinte" << endl;
  cout << q << " Billete(s) de quince" << endl;
  cout << d << " Billete(s) de diez" << endl;
  cout << c << " Billete(s) de cinco" << endl;
  cout << u << " Billete(s) de uno" << endl;
}

Codicioso, no recursivo XD

//set de monedas
private readonly COINS: Array<number> = [20, 10, 5, 2, 1];

  private _calculateMoney = (moneyToReturn: number): Map<number, number> => {
    let map = new Map<number, number>();
    for (let i = 0; i < this.COINS.length; i++) {
      const _coins = moneyToReturn / this.COINS[i];
      
      if (_coins >= 1) {
        map.set(this.COINS[i], Math.floor(_coins));
        moneyToReturn = moneyToReturn % this.COINS[i]
      }
    }
    return map;
  }

Solucion al problema en JAVA, lo que hice para entenderle mejor a la recursividad del problema fue solucionar el problema de manera ITERATIVA con un bucle for y despues hacer otro metodo que lo solucione de manera RECURSIVA ambas formas implementando un algoritmo GREEDY

//Este metodo (1) (de manera iterativa) regresa la cantidad de monedas 
        //y sus denominaciones a devolver dependiendo del cambio "cambio".
        Change greedyChange(int cambio) {
            Change ch = new Change();
            int num;
            int monedas = 0;
            for (int i = 3; i > -1; i--) {
                num = cambio / this.coinSet[i];
                if (num > 0) {
                    monedas += num;
                    cambio -= (num * this.coinSet[i]);
                    switch (this.coinSet[i]) {
                        case 20:
                            ccant20 += monedas;
                            ch.setCcant20(ccant20);
                            break;
                        case 10:
                            ccant10 += monedas - ccant20;
                            ch.setCcant10(ccant10);
                            break;
                        case 5:
                            ccant5 += monedas - ccant20 - ccant10;
                            ch.setCcant5(ccant5);
                            break;
                        case 1:
                            ccant1 += monedas - ccant20 - ccant10 - ccant5;
                            ch.setCcant1(ccant1);
                            break;
                    }
                }
            }
            ch.setChange(monedas);
            return ch;
        }

        //Este metodo (2) (de manera recursiva) regresa la cantidad de monedas 
        //y sus denominaciones a devolver dependiendo del cambio "change". 
        void greedyRecursivo(int change,int size) {
           
            setChange(change);
            if (getChange() == 0 || getChange() < 0) {
                
                return;
            }

            int numMonedas = 0, numTotal = 0;

            numTotal = (getChange() / this.coinSet[size - 1]);

            if (numTotal > 0) {
                numMonedas += numTotal;
                change -= (numTotal * this.coinSet[size - 1]);
                setChange(change);
                switch (this.coinSet[size - 1]) {
                    case 20:
                        this.cant20 += numMonedas;
                        setCant20(cant20);
                        break;
                    case 10:
                        this.cant10 += numMonedas;
                        setCant10(cant10);
                        break;
                    case 5:
                        this.cant5 += numMonedas;
                        setCant5(cant5);
                        break;
                    case 1:
                        this.cant1 += numMonedas;
                        setCant1(cant1);
                        break;
                }
            }
            
            greedyRecursivo(getChange(),size - 1);
           int chan =  cant20+cant10+cant5+cant1;
           if(change == 0){
               System.out.println("Cantidad de monedas utilizadas para dar feria: " + chan + ", " +
                    cant20 + " de $20, " + + cant10 + " de $10, "+  cant5 + " de $5, "+
                    cant1 + " de $1.");
           }
            
        }
        
        

        @Override
        public String toString() {
            return "Cantidad de monedas utilizadas"
                    + " para dar feria: " + change + ", " + ccant20 + " de $20" + ", " + ccant10 + " de $10"
                    + ", " + ccant5 + " de $5" + ", " + ccant1 + " de $1";
        }```

Con ambos obtuve el resultado:
**Cantidad de monedas utilizadas para dar feria: 3, 1 de $20, 1 de $10, 1 de $5, 0 de $1.**
para un cambio de $35

COINS = [50, 25, 15, 10, 5, 2, 1]

def Change(debt, change):                       # Greedy
    if debt > 0:
        for index in range(0, len(COINS)):
            num = int(debt/COINS[index])
            if num > 0:
                debt -= num*COINS[index]
                change.append((num,COINS[index]))
                del COINS[index]
                return Change(debt, change)
            

if __name__ == '__main__':
    debt = int(input())
    change = list()
    Change(debt, change)
    print(change)

La verdad que para este ejercicio me perdí porque no sé C++. Pero hice esto en JavaScript que no sé si está bien, pero anda:

const result = [0, 0, 0, 0, 0];
const coins = [50, 25, 10, 5, 1];

function greedyChange(amount, coinSet) {
	if (amount > 0) {
		for (let i = 0; i < coinSet.length; i++) {
			if (amount - coinSet[i] >= 0) {
				result[i]++;
				return greedyChange(amount - coinSet[i], coinSet);
			}
		}
	}
}

Yo lo hice asi:

#include <iostream>
#include <climits>
using namespace std;

int greedyChange(int coinSet[], int n, int N)
{
  if (n==0)
  {
    return 0;
  }
  if(N<0)
  {
    return INT_MAX;
  }
  int coins = INT_MAX;
  //RECORREMOS TODO EL SET DE MONEDAS  PARA DAR CAMBIO
  for(int i = 0; i<n; i++)
  {
    int res = greedyChange(coinSet, n, N-coinSet[i]);
    if(res != INT_MAX)
    {
      coins = min(coins, res+1);
    }
  }
  return coins;
}

 int main(int argc, char const *argv[])
 {
  int valor;
  int i;
  int coinSet[] = {1, 5, 10, 15, 20, 50};
  int n = sizeof(coinSet)/sizeof(coinSet[0]);

  int N = 27;

  cout << "El minimo de monedas para dar cambio es: "
          << greedyChange(coinSet, n, N);
  for(i=0; i<n; i++)
  {
    valor = coinSet[i];
    printf("%i \n", valor);
  }

  return 0;
}```

Mi solución en C++:

#include <iostream>

using namespace std;

int greedyChange(int coinSet[], int lenCoinSet,  int money){
    int change = 0;
    static int i = 0;

    if(i >= lenCoinSet){
        return 0;
    }
    while(money - coinSet[i] >= 0){
        change++;
        money -= coinSet[i];
    }
    i++;
    return change + greedyChange(coinSet, lenCoinSet, money);
}

int main(int argc, char const *argv[]){

    int coinSet[]={20, 15, 10, 5, 1};
    int lenCoinSet = sizeof(coinSet)/sizeof(coinSet[0]);
    int money = 30;

    cout << "The minimun number of coins to get your change is: " 
            << greedyChange(coinSet, lenCoinSet, money)<<endl;
    return 0;
}

Este es mi código con Python, algo así muy básico para una tiendita

def greedy_change(res, coins, client_coins):
    if res == 0:
        return client_coins
    else:
        for key, value in coins.items():
            if res >= key and value > 0:
                client_coins[key] += 1
                coins[key] = value - 1
                res -= key
                break                

        greedy_change(res, coins, client_coins)
    

if __name__ == "__main__":

    while True:
        amount = int(input('Total amount: '))
        payment = int(input('Customer payment: '))

        res = payment - amount
        
        coins = {
            20: 4,
            10: 5,
            5: 10,
            1: 3
        }

        total_money = 0
        for key, value in coins.items():
            total_money += (key * value)
        if amount > payment:
            print('------------------------------------------------------------------')
            print('The customer\'s payment must be greater than the amount to be paid')
            print('------------------------------------------------------------------')

        elif total_money < res:
            print('----------------')
            print('Not enough money. Go with the supervisor for more money.')
            print('----------------')
        else:
            client_coins = coins.copy()

            for key,value in client_coins.items():
                client_coins[key] = 0
            
            greedy_change(res, coins, client_coins)

            result = []

            for key, value in client_coins.items():
                if value > 0:
                    result.append(f'{value} coins of ${key} pesos')

            print('Return to customer:\n')
            for i in result:
                print(f'    {i}')
            print(f'\n    Total: ${res}')
            exit()

En cpp

Este es otra forma de resolverlo sin usar ciclos, es en swift

var position = 0
var total = [Int]()
callGreedyAlgorithm(subtotal: 34, cash: 200)
func callGreedyAlgorithm(subtotal: Int, cash: Int){
    greedyAlgorithm(remaining: cash - subtotal)
    print(total)
}
func greedyAlgorithm(remaining: Int) {
    if remaining > 0 {
        if remaining < coinSet[position] {
            position += 1
            greedyAlgorithm(remaining: remaining)
        } else {
            total.append(coinSet[position])
            greedyAlgorithm(remaining: remaining - coinSet[position])
        }
    }
}```

Creo que el problema esta planteado de manera muy irreal. En la vida real, puede que nos quedemos sin monedas de 5. O, por ejemplo, digamos que queremos entregar $26 y nuestro coinset es [2, 5, 20].
En este caso, entregar 20 y luego 5 nos deja sin solucion; sin embargo, si damos 20, 2, 2, 2, entonces estaria solucionado.
Buen problema para practicar!

Aquí el código en C, por si a alguien le interesa.

/*
Buscaremos el minimo de monedas posible para obtener el cambio total N,
tomando monedas del set monedas coinSet[]
necesitamos un auxiliar "res" para que funcione
crear una funcion recursiva para encontrar el valor
y retornar "monedas necesarias para el cambio"
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int greedyChange(int coinSet[], int n, int N);

int greedyChange(int coinSet[], int n, int N)
{
    if(N==0)
    {
        return 0;
    }

    if (N < 0)
    {
        return 9999;
    }

    int coins = 9999;
    int res = 0;
    int i = 0;

    for(i=0; i<n; i++)
    {
        res = greedyChange(coinSet, n, N-coinSet[i]);
        if(res != 9999)
        {
            if(coins <= res+1)
            {
                coins = coins;
            }else
            {
                coins = res+1;
            }
        }
    }

    return coins;
}

int main(int argc, const char * argv[])
{
    int exchange = 0;
    int coinSet[] = {1, 5, 10, 15, 20};
    int n = sizeof(coinSet)/sizeof(coinSet[0]);

    int value = 27;

    exchange = greedyChange(coinSet, n, value);

    printf("El total de monedas es: %d", exchange);

    return 0;
}

#include <iostream>
#include <climits>

using namespace std;

int greedyChange( int coinSet[], int n, int N ) {
    // Ya no debemos nada
    if ( N == 0 ) 
        return 0;
    
    // Algo paso mal, regresamos de mas
    if ( N < 0 )
        return INT_MAX;
    
    // Inizialisar el coins
    int coins = INT_MAX;


    // Recorremos el set de monedas
    for ( int i = 0; i < n; i++ ) {
        // Llamar recursivamente a la funcion con el cambio de alguan moneda en la coinset
        int res = greedyChange( coinSet, n, N - coinSet[i] );
        if( res != INT_MAX ) {
            // +1 el paso extra (moneda usada)
            coins = min(coins, res + 1);
        }
    }

    return coins;
    
}

int main( int argc, char const *argv[] ) {
    int coinSet[] = {1, 5, 10, 15, 20};
    int n = sizeof(coinSet) / sizeof(coinSet[0]);

    int N = 27;

    cout << "El minimo de monedas para dar cambio es: " << greedyChange(coinSet, n, N);
}```

Si usan mac OS pueden compilar de esta manera:

$ g++ greedySort.cpp -o greedySort

Luego lo ejecutan así:

./greedySort 

En JavaScript

function greedyChange(coinSet, size, change)
{
  if(size >= 1)
  {
    if(change >= coinSet[size - 1])
    {
      auxChange = Math.floor(change / coinSet[size - 1])
      change -= (auxChange * coinSet[size - 1])
      coinSet[size - 1] = auxChange
      greedyChange(coinSet, size - 1, change)
    }else {
      coinSet[size - 1] = 0;
      greedyChange(coinSet, size - 1, change)
    }
  }
}

const coinSet = [1, 2, 5, 10, 20, 50]
let change = 13
let changeSet = coinSet.slice()
greedyChange(changeSet, changeSet.length, change)
for(i = 0; i < coinSet.length; i++)
{
  console.log(`${changeSet[i]} bills of ${coinSet[i]}`)
}

Se realiza modificación para que también se imprima la denominación de las monedas.

<code>
/*
Buscaremos el minimo de monedas posile para obtener el cambio total,
tomando monedas del set monedas
necesitamos un auxiliar "res" stack recursivo
crear una función recursiva para encontrar el valor
y retornar monedas necesarias para el cambio

    Se agregan lineas para poder guardar las denominaciones de las monedas.
*/

#include <iostream>
#include <climits>
using namespace std;

int greedyChange(int coinSet[], int n, int N,int orden[]){
    if(N==0){
        return 0;
    }
    if(N<0){
        return INT_MAX;
    }
    int coins = INT_MAX;
    //recorremos todo nuestro set de monedas AKA opciones para dar cambio
    for(int i = 0; i < n; i++)
    {
        int res = greedyChange(coinSet, n, N-coinSet[i], orden);
        if(res != INT_MAX){
            coins = min(coins, res + 1);
            orden[res] = coinSet[i];            
        }
    }
    return coins;
}

int main(int argc, char const *argv[])
{
    int coinSet[]={1,5,10,15,20};
    int orden_operaciones[20];
    int n = sizeof(coinSet)/sizeof(coinSet[0]);
    int N = 27;

    int resultado = greedyChange(coinSet, n, N, orden_operaciones);

    cout << "Total: " << N << "\nel minimo de monedas para dar cambio es:"<< resultado << "\n";

    for(int i=0; i < resultado; i++)
        printf("Moneda: %d\n", orden_operaciones[i]);  

    return 0;

}

SALIDA
Total: 27
el minimo de monedas para dar cambio es:4
Moneda: 1
Moneda: 1
Moneda: 5
Moneda: 20

#include <iostream>
#include <climits>
using namespace std;

//-----------------------------------------------------------------------------
int greedyChange(int coinSet[], int n, int N,int order[]){
    if(N==0){
        return 0;
    }
    if(N<0){
        return INT_MAX;
    }
    int coins = INT_MAX;
    //recorremos todo nuestro set de monedas AKA opciones para dar cambio
    for(int i = 0; i < n; i++)
    {
        int res = greedyChange(coinSet, n, N-coinSet[i], order);
        if(res != INT_MAX){
            coins = min(coins, res + 1);
            order[res] = coinSet[i];            
        }
    }
    return coins;
}

//-----------------------------------------------------------------------------
int main()
{
    int coinSet[]={1,5,10,15,20};
    int operationOrder[20];
    int n = sizeof(coinSet)/sizeof(coinSet[0]);
    int N = 27;
    int resultado = greedyChange(coinSet, n, N, operationOrder);
    cout << "Total: " << N << "\nel minimo de monedas para dar cambio es:"<< resultado << "\n";
    for(int i=0; i < resultado; i++)
        printf("Moneda: %d\n", operationOrder[i]);  
    return 0;
}

#include <iostream>
#include <climits>
using namespace std;

int greedyChange(int coinSet[], int t, int d, int cam[])
{
  if(d == 0)
    return 0;

  if(d < 0)
    return INT_MAX;
    
  int coins = INT_MAX;
    
  for(int i = 0; i < t; i++)
  {
    int res = greedyChange(coinSet, t, d - coinSet[i], cam);

    if(res != INT_MAX)
    {
      coins = min(coins, res + 1);
      cam[res] = coinSet[i];            
    }
  }
  return coins;
}

int main(int argc, char const *argv[])
{
  int coinSet[] = {100, 500, 1000};
  int cambio[20];
  int tam = sizeof(coinSet) / sizeof(coinSet[0]);
  int dinero;

  cout << "Ingrese un valor: ";
  cin >> dinero;

  cout << "\nEl minimo de monedas para dar cambio es: "<< greedyChange(coinSet, tam, dinero, cambio);
  
  for(int i=0; i < greedyChange(coinSet, tam, dinero, cambio); i++)
    printf("\nDinero: %d", cambio[i]);  
  
  return 0;
}

#include<iostream>
#include<climits>

using namespace std;

int greedyChange(int coinSet[], int n, int N)
{
	if(N == 0)
	{
		return 0;
	}
	
	if(N<0)
	{
		return INT_MAX;
	}
	
	int coins = INT_MAX;
	
	//recorremos todo el set de monedas  AKA opcciones para dar cambio
	for(int i=0; i<n; i++)
	{
		int res = greedyChange(coinSet, n, N-coinSet[i]);
		if(res != INT_MAX)
		{
			coins = min(coins, res+1);
		}
	}
	
	return coins;
}


int main (int argc, char const *argv[])
{
	int coinSet[] = {1,5,10,15,20};
	int n = sizeof(coinSet) / sizeof(coinSet[0]);
	
	int N = 27;
	
	cout<< "El minimo de monedas  para dar cambio es: \n" << greedyChange(coinSet, n, N	);
	
	
	return 0;
}```

/*
 Buscar mínimo de monedas posibles para obtener el cambio total
 Tomamos monedas del set de monedas coinSet[]
 Usamos un auxuliar "res" -> stack recursivo
 Crear función recursiva para encontrar el valor
 Ratornamos monedas necesarias para el cambio
*/

#include <iostream>
#include <climits>

using namespace std;

int greedyChange(int coinSet[], int coinSetSize, int debt) {
    if(debt==0) return 0;
    if(debt<0) return INT_MAX;
    int coins = INT_MAX;

    // Recorremos todo nuestro coinSet
    for(int i=0; i<coinSetSize; i++) {
        int res = greedyChange(coinSet, coinSetSize, debt-coinSet[i]);
        if(res != INT_MAX) {
            coins = min(coins, res+1);
        }
    }

    return coins;
}

int main(int argc, char const *argv[])
{
    int coinSet[] = {1, 5, 10, 15, 20};
    int coinSetSize = sizeof(coinSet) / sizeof(coinSet[0]);
    int debt = 27;
    cout << "Minimum coins is: " << greedyChange(coinSet, coinSetSize, debt) << endl;
    return 0;
}

Listo, sigo pensando que la recursión no es lo más óptimo por la cantidad de memoria que usa. En este algoritmo si pones valores altos tarda demasiado en dar una respuesta.

#include <iostream>
#include <climits>

using namespace std;

int greedyChange( int coinSet[], int n, int dinero, int monedaEntregada[] )
{
    size_t i;
    int res = 0;

    if( dinero == 0 )
    {
        return 0;
    }
    if( dinero < 0 )
    {
        return INT_MAX;
    }

    int coins = INT_MAX;

    // Recorremos todo el setCoins
    for(i =0; i<n; i++)
    {
        int res = greedyChange(coinSet, n, dinero - coinSet[i], monedaEntregada ); // Stack recursivo

        if(res != INT_MAX) // Usa solo los valores q no den error
        {
            coins = res+1;
            monedaEntregada[res] = coinSet[i];
        }
    }

    return coins;
}

int main(int argc,  char const *argv[])
{
    size_t i;

    int coinSet[] = {1,5,10,15,20};
    int monedasEntregadas[10];
    int n = sizeof(coinSet)/sizeof(coinSet[0]);
    int cantidadMonedas = 0;
    int dinero = 0;

    cout << "Ingrese un Valor: ";
    cin >> dinero;

    if(dinero<0)
    {
        cout << "Valor incorrecto" << endl;
        return 0;
    }

    cout << endl << "El cambio para " << dinero << " con el minimo de monedas es: ";
    cantidadMonedas = greedyChange(coinSet, n, dinero, monedasEntregadas);
    cout << cantidadMonedas << endl;

    cout << endl << "  Entregar " << endl;

    for(i = cantidadMonedas; i > 0; i--)
    {
        cout << "Moneda: " << monedasEntregadas[i-1] << endl;
    }

    return 0;
}

INT_MAX realmente puede llegar a desbordarse hmmmmmmm, bueno al menos ya tengo una forma mas eficiente de dar cambio XD no pienso desperdiciar mi galería de imágenes así que las subo de nuevo XD
![](

![](

![](

En C#

using System;

namespace GreedyCoinChange
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] coinSet={1,5,10,15,20};
            int n = coinSet.Length;
            int N = 27;
            Console.WriteLine("El mínimo de monedas para dar cambion es: ");
            Console.Write(greedyChange(coinSet, n, N));
        }

        private static int greedyChange(int[] coinSet, int n, int N )
        {
            if (N==0)
                return 0;
            if (N<0)
                return Int16.MaxValue;
            int coins = Int16.MaxValue;
            for (int i = 0; i < n; i++)
            {
                 int res = greedyChange(coinSet, n, N - coinSet[i]);
                 if(res != Int16.MaxValue)
                    coins = Math.Min(coins, res+1);
            }
             return coins;
        }
    }
    
}

En GO

package main

import (
	"fmt"
	"strconv"
)

func main() {

	coinSet := []int{50, 20, 10, 5, 1}
	valor := 127

	num, monedas := coinChangeCount(valor, coinSet)
	println("Número de monedas: " + strconv.Itoa(num))
	for _, moneda := range monedas {
		fmt.Printf("%d ", moneda)
	}
	fmt.Printf("\n")
}

func coinChangeCount(valor int, coinSet []int) (int, []int) {
	if valor == 0 {
		return 0, nil
	}
	for _, coin := range coinSet {
		if valor >= coin {
			total, coins := coinChangeCount(valor-coin, coinSet)
			coins = append(coins, coin)
			return 1 + total, coins
		}
	}
	return 1, nil
}

#include <iostream>
#include <climits>
using namespace std;

int greedyChange(int coinSet[], int n,  int N){
    if (N==0)
        return 0;
    
    if (N<0)
        return INT_MAX;

    int coins = INT_MAX;
//recorremos todo nuestro set de moneas AKA opciones para dar cambio
    for(int i = 0; i<n; i++)
    {
        int res = greedyChange(coinSet, n, N - coinSet[i]);
        if(res != INT_MAX)
            coins = min(coins, res+1);
    }
    
    return coins;
}

int main(int argc, char const *argv[])
{
    int coinSet[]={1,5,10,15,20};
    int n = sizeof(coinSet)/sizeof(coinSet[0]);

    int N = 27;

    cout << "el minimo de monedas para dar cambio es: " 
            << greedyChange(coinSet, n, N);
    return 0;
}

Mi código en JavaScript para entregar los billetes:

class Billete {
  constructor(Valor,Cantidad){
    this.Valor = Valor;
    this.Cantidad = Cantidad;
  }
}

function Cambio(coinSet,act,debt,change){
  if(debt == 0){
    for(var i = 0; i<change.length;i++){
      if(change[i].Valor && change[i].Cantidad){
        console.log("Se entregan " + change[i].Cantidad + " billetes de: " + change[i].Valor);
      }
    }
    return console.log("Cambio entregado!");
  }
  if(debt > 0){
    if(act>= coinSet.length){
       return console.log("disculpa no puedo entregarte ese valor :(")
    }
    var temp = Math.floor(debt/coinSet[act]);
    change[act] = new Billete(coinSet[act], temp);
    debt = debt - (coinSet[act] * temp)

  }
  Cambio(coinSet,act + 1, debt, change);
}

var caja = [100,50,20,10,5,1];

var deuda = 289 ;
var vuelto = [];

Cambio(caja,0,deuda,vuelto);

Mi solución en javascript

const coins = [50, 20, 10, 5, 1];

const giveChange = (money, spent) => {
  if (money < spent) {
    console.log("You have spent more than you've paid");
    return;
  }
  const result = calculate(money - spent, 0, []);
  console.log("Your change is: " + result);
};

const calculate = (remaining, position, change) => {
  if (remaining === 0) {
    return change;
  }
  if (remaining >= coins[position]) {
    remaining -= coins[position];
    change.push(coins[position]);
    return calculate(remaining, position, change);
  } else {
    return calculate(remaining, ++position, change);
  }
};

giveChange(153, 10);

en python sencillo directo pero no codicioso,
el problema del morral hubiera sido mas un caso practico para esta clase

def greedy_change(cambio, COINS): 
    
    list_coin=dict()
    for i in COINS: 
        if cambio>=i: 
            temp_entero=cambio//i
            list_coin[i]=temp_entero
            cambio=cambio%i
    return list_coin


cambio=47
COINS = [ 20,15,  10, 5, 3, 1]
COINS.sort(reverse=True)
dic_gc=greedy_change(cambio, COINS)
for x, y in dic_gc.items() : print(y, " coins of ", x)

resultado:

2  coins of  20
1  coins of  5
2  coins of  1

Mi versión en C resuelta con la misma lógica del algoritmo y recursividad.
|

#include <stdio.h>
#include <stdlib.h>

int USD_Amount;
int coinsAmount[] = { 0, 0, 0, 0, 0, 0};
int coin_set[] = {1 , 5 , 10 , 20 , 50 , 100};
int n = sizeof(coin_set)/sizeof(coin_set[0]);

int Greedy_CoinChange(int coin_set[], int i ,int N) 
{
  if(N==0)
  {
    return 0;
  }

  if  (N < 0)
  {
    return -2;
  }

  if(coin_set[i] > N) {
      i--;
  } else {
      coinsAmount[i]++;
      USD_Amount++;
      N = N-coin_set[i];
  }
  Greedy_CoinChange(coin_set, i , N);
  
}

void imprimir() {
  for ( int j = 0; j < n; j++) {
      printf("Amount of Bills of %d: %d\n",coin_set[j], coinsAmount[j]);
  }
  printf("\nTotal of Bills: %d\n",USD_Amount);
}


int main (int argc, char *argv[]) 
{
    int i = n-1;
    int N;
    printf("Amount?: ");
    scanf("%d", &N);
    printf("\n");

    Greedy_CoinChange(coin_set, i , N);

    imprimir();

   return 0;
}

Consola:

Amount?: 137

Amount of Bills of 1: 2  
Amount of Bills of 5: 1  
Amount of Bills of 10: 1 
Amount of Bills of 20: 1 
Amount of Bills of 50: 0 
Amount of Bills of 100: 1

Total of Bills: 6

Este es mi código en C++ con el número ingresado por el usuario.

#include <iostream>

using namespace std;
int amount_coin;
int coin_20;
int coin_15;
int coin_10;
int coin_5;
int coin_1;

int Greedy_CoinChange(int coins[], int n ,int N) {
    int i = n - 1;
    if(N == 0){
        return 0; // indicar que no hay valores de moneda para 0
    }
    if( N < 0){
        return -2; //indicar valor incorrecto
    }
    while(N!=0) {
        if(coins[i] > N) {
            i--;
        } else {
            switch(coins[i]){
                case 20: coin_20++;
                break;
                case 15: coin_15++;
                break;
                case 10: coin_10++;
                break;
                case 5: coin_5++;
                break;
                case 1: coin_1++;
                break;
            }
            cout << "$ " << coins[i] << "\t"; // imprime la moneda que va a elegir 
            amount_coin++;          // cuantificar la cantidad de moneda a devolver
            N = N-coins[i];
        }
    }
  cout << endl;
  
}

int main(){
    int N;
    cout << "Ingrese el valor a generar cambio: $";
    cin >> N; 
    int coins[]={1,5,10,15,20};
    int n = sizeof(coins)/sizeof(coins[0]);
    Greedy_CoinChange(coins,n,N);

    cout << "Cantidad total de Cambio => " << amount_coin << endl;
    cout << "Cantidad total de $ " << coins[0] << " es: " << coin_1 << " billetes." << endl;
    cout << "Cantidad total de $ " << coins[1] << " es: " << coin_5 << " billetes." << endl;
    cout << "Cantidad total de $ " << coins[2] << " es: " << coin_10 << " billetes." << endl;
    cout << "Cantidad total de $ " << coins[3] << " es: " << coin_15 << " billetes." << endl;
    cout << "Cantidad total de $ " << coins[4] << " es: " << coin_20 << " billetes." << endl;
    return 0;
}

No sé si sólo soy yo, pero si le entregas a la “máquina” (Valor de N) una cantidad mayor a $80, el algoritmo no me regresa nada.

Este video explica mucho mejor el problema y porque es parte de la programación dinámica.
https://www.youtube.com/watch?v=jgiZlGzXMBw

Llamar a la macro sizeof una “función” me deja un poco loco…

wow… Fue un algoritmo muy dificil de entender!!
El hecho de que la recursividad funcione en forma de muchas capas, transporta tu mente a multiples dimeciones y te hace analisar el proceso capa por capa… y eso es IMPOSIBLE DE SEGUIR DE FORMA MENTAL.
La unica forma de comprenderlo es de forma visual utilizando los Print Statement a nuestro favor. y obviamente con N (el cambio de debemos dar) pequeño. y solo dos tipos de monedas y luego observar como funciona la logica

#include <iostream>
#include <climits>
using namespace std;

int greedyChange(int coinSet[], int n,  int N){
    if (N==0)
        return 0;
    
    if (N<0)
        return INT_MAX;

    int coins = INT_MAX;
//recorremos todo nuestro set de moneas AKA opciones para dar cambio

    
        for(int i = 0; i<n; i++)
        {
            int res = greedyChange(coinSet, n, N - coinSet[i]);
            // como tenemos solo dos tipos de monedas (1 y 5) solo hara dos ciclos por cada capa.
            cout << "ciclo = " << i << endl;
            // con esta linea de codigo podremos observar en que capa estamos
            cout << "capa Nro.= " << N << endl;
            // aqui podremos observar como estan interactuando los res.
            cout << "res = " << res << endl;
        
            if(res != INT_MAX)
            {
            coins = min(coins, res+1);
            }
            // finalmente observaremos como va variando los coins
            cout << "coins = " << coins << endl << endl;
        }



    return coins;
}

int main(int argc, char const *argv[])
{
    int coinSet[]={1,5};
    int n = sizeof(coinSet)/sizeof(coinSet[0]);
    

    int N = 7;

    cout << "el minimo de monedas para dar cambio es: " 
            << greedyChange(coinSet, n, N);
    return 0;
}```

My versión en python

import random

monedas = [200, 100, 50, 20, 10, 5, 1]

def run(cantidad, m):
    a = cantidad // monedas[m]
    cantidad = cantidad % monedas[m]
    if a != 0:
        print(a, 'moneda(s) de ', monedas[m])
    if cantidad == 0:
        return a * monedas[m]

    return a * monedas[m] + run(cantidad, m+1)


if __name__ == '__main__':
    cantidad = random.randint(0, 100)
    print('Total a pagar: ', cantidad)
    den = int(input('Cantidad introducida: '))
    print('Su cambio es: ', run(den - cantidad, m=0))

Rehice el algoritmo para entenderlo mejor.

#include<stdio.h>

void coinchange(int coinset[], int value, int count){    
    int solution[count];
    int moneyback=value;
    for (int i = 0; i < count; i++)
    {
        solution[i]=0;
    }
    int index=0;
    
    while (value > 0 && index < count)    
    {
        if (coinset[index]> value)            
            index++;
        else {
            solution[index]++;
            value-=coinset[index];                
        }         
    }
    if (value>0)
        printf("Monedas insuficientes para %d... falta %d",moneyback,value);    
    else{
        printf("Monedas usadas para dar vuelto de %d \n",moneyback);
        for (int i = 0; i < count; i++)
        {
            if (solution[i]>0)
                printf("- %d  moneda(s) de %d \n", solution[i],coinset[i]);
        }
        
    }
    
}

int main(int argc, char const *argv[])
{
    int coinSet[]={20,15,10,5,1};
    int moneyback=27;
    int count= sizeof(coinSet)/sizeof(coinSet[0]);
    coinchange(coinSet, moneyback,count);
    return 0;
}

Hola Amig@s

Me ha costado entender la lógica de los algoritmos, pero haciendo las pruebas de escritorio se entienden un poco mas fácil, ahora l a que no entendía muy bien era la prueba de escritorio de una función recursiva.

Les dejo el siguiente video que explica como hacer dicha prueba

https://www.youtube.com/watch?v=K5OktsgEEOQ

como puedo solucionar

Les dejo una implementación de este algoritmo en JS
https://realraulmar.github.io/cajeroSimple/

Código implementado en Java. Tengo duda si se considera recursivo o Greedy Algorithm si se utiliza el comando break;. Espero alguien me pueda retroalimentar. Gracias.

public class Main {

    public static void main(String[] args) {
	// write your code here
        int[] coinSet = {20,10,5,1};
        int N = 214;
        GreedyChange greedyChange = new GreedyChange();
        greedyChange.greedyChange(coinSet,N);
        greedyChange.printChange();
    }
}

import java.util.ArrayList;
import java.util.List;

public class GreedyChange {
    private List<Integer> coins = new ArrayList<>();

    public void greedyChange(int[] coinSet, int change) {
        if(change<=0){
            return;
        }
        for(int i=0; i<coinSet.length; i++){
            if(change-coinSet[i] >= 0){
                coins.add(coinSet[i]);
                change -= coinSet[i];
                greedyChange(coinSet,change);
                break;
            }
        }
    }

    public void printChange() {
        System.out.println("The change is being distributed in " + coins.size() + " coins in the following" +
                " way: ");
        int sum = 0;
        for (int i = 0; i < coins.size(); i++) {
            if (i == coins.size() - 1) {
                System.out.print( "$" +coins.get(i));
            } else {
                System.out.print("$" + coins.get(i) + " + ");
            }
            sum += coins.get(i);
        }
        System.out.print(" = $" + sum);
    }

}

Código implementado en Java. Tengo duda si se considera recursivo o Greedy Algorithm si se utiliza el comando break; para no repetir iteraciones. Espero alguien me pueda retroalimentar. Gracias.

public class Main {

    public static void main(String[] args) {
	// write your code here
        int[] coinSet = {20,10,5,1};
        int N = 214;
        GreedyChange greedyChange = new GreedyChange();
        greedyChange.greedyChange(coinSet,N);
        greedyChange.printChange();
    }
}

import java.util.ArrayList;
import java.util.List;

public class GreedyChange {
    private List<Integer> coins = new ArrayList<>();

    public void greedyChange(int[] coinSet, int change) {
        if(change<=0){
            return;
        }
        for(int i=0; i<coinSet.length; i++){
            if(change-coinSet[i] >= 0){
                coins.add(coinSet[i]);
                change -= coinSet[i];
                greedyChange(coinSet,change);
                break;
            }
        }
    }

    public void printChange() {
        System.out.println("The change is being distributed in " + coins.size() + " coins in the following" +
                " way: ");
        int sum = 0;
        for (int i = 0; i < coins.size(); i++) {
            if (i == coins.size() - 1) {
                System.out.print( "$" +coins.get(i));
            } else {
                System.out.print("$" + coins.get(i) + " + ");
            }
            sum += coins.get(i);
        }
        System.out.print(" = $" + sum);
    }

}```

Código implementado en Java. Tengo duda si se considera Greedy Algorithm o recursivo al utilizar el comando break;. Espero alguien me pueda ayudar con eso. Gracias.

public class Main {

    public static void main(String[] args) {
	// write your code here
        int[] coinSet = {20,10,5,1};
        int N = 214;
        GreedyChange greedyChange = new GreedyChange();
        greedyChange.greedyChange(coinSet,N);
        greedyChange.printChange();
    }
}

import java.util.ArrayList;
import java.util.List;

public class GreedyChange {
    private List<Integer> coins = new ArrayList<>();

    public void greedyChange(int[] coinSet, int change) {
        if(change<=0){
            return;
        }
        for(int i=0; i<coinSet.length; i++){
            if(change-coinSet[i] >= 0){
                coins.add(coinSet[i]);
                change -= coinSet[i];
                greedyChange(coinSet,change);
                break;
            }
        }
    }

    public void printChange() {
        System.out.println("The change is being distributed in " + coins.size() + " coins in the following" +
                " way: ");
        int sum = 0;
        for (int i = 0; i < coins.size(); i++) {
            if (i == coins.size() - 1) {
                System.out.print( "$" +coins.get(i));
            } else {
                System.out.print("$" + coins.get(i) + " + ");
            }
            sum += coins.get(i);
        }
        System.out.print(" = $" + sum);
    }

}

Código implementado en Java, tengo duda si cuenta como Greedy Algorithm la utilización de break; para repetir iteraciones. Espero alguien me pueda dar retroalimentación. Gracias.

public class Main {

    public static void main(String[] args) {
	// write your code here
        int[] coinSet = {20,10,5,1};
        int N = 214;
        GreedyChange greedyChange = new GreedyChange();
        greedyChange.greedyChange(coinSet,N);
        greedyChange.printChange();
    }
}

import java.util.ArrayList;
import java.util.List;

public class GreedyChange {
private List<Integer> coins = new ArrayList<>();

public void greedyChange(int[] coinSet, int change) {
    if(change<=0){
        return;
    }
    for(int i=0; i<coinSet.length; i++){
        if(change-coinSet[i] >= 0){
            coins.add(coinSet[i]);
            change -= coinSet[i];
            greedyChange(coinSet,change);
            break;
        }
    }
}

public void printChange() {
    System.out.println("The change is being distributed in " + coins.size() + " coins in the following" +
            " way: ");
    int sum = 0;
    for (int i = 0; i < coins.size(); i++) {
        if (i == coins.size() - 1) {
            System.out.print( "$" +coins.get(i));
        } else {
            System.out.print("$" + coins.get(i) + " + ");
        }
        sum += coins.get(i);
    }
    System.out.print(" = $" + sum);
}

}

The change is being distributed in 15 coins in the following way:
$20 + $20 + $20 + $20 + $20 + $20 + $20 + $20 + $20 + $20 + $10 + $1 + $1 + $1 + $1 = $214
Process finished with exit code 0