Bienvenido al Curso

1

Introducci贸n al curso b谩sico de algoritmos y estructuras de datos

Introducci贸n a los algoritmos

2

驴Qu茅 entiende una computadora?

3

Lenguajes de programaci贸n

4

Estructuras de datos

5

驴Qu茅 es un algoritmo?

6

Metodolog铆a para la construcci贸n de un algoritmo

7

Variables y tipos de datos

8

User defined data types

9

Instalando Ubuntu Bash en Windows

10

Creando nuestro user defined data type

11

Abstract Data Types b谩sicos: Lists, Stacks, Queues

12

Explicaci贸n gr谩fica Data Types b谩sicos

13

Glosario de funciones para Abstract Data Types

14

Clases y objetos

15

Creando tu primera Queue: Arrays

16

Creando tu primera Queue: implementaci贸n.

17

Creando tu primera Queue: implementar la funci贸n enQueue

18

Creando tu primera Queue: implementar la funci贸n deQueue

19

Creando tu primera Queue: main code

Algoritmos de ordenamiento

20

Algoritmos de ordenamiento

21

Bubble sort

22

Bubble sort: implementaci贸n

23

Bubble sort: main code

24

Insertion sort

25

Desaf铆o: implementa un algoritmo de ordenamiento

Recursividad

26

Recursividad

27

La funci贸n Factorial, calculando el factorial recursivamente

28

Manejo de cadenas de caracteres

29

Arte: Generando arte recursivo

Divide and conquer y programaci贸n din谩mica

30

Divide and Conquer (divide y vencer谩s)

31

Qu茅 es la programaci贸n din谩mica (divide y vencer谩s v2.0)

32

MergeSort

33

Desaf铆o: Buscar el algortimo m谩s r谩pido de sort

34

Implementando QuickSort con Python

35

Implementando QuickSort con Python: main code

Algoritmos 'Greedy'

36

Qu茅 son los Greedy Algorithm

37

Ejercicio de programaci贸n greedy

38

Ejercio de programaci贸n greedy: main code

Grafos y 谩rboles

39

Grafos y sus aplicaciones

40

脕rboles

驴C贸mo comparar Algoritmos?

41

C贸mo comparar algoritmos y ritmo de crecimiento

驴Qu茅 sigue?

42

Cierre del curso y siguientes pasos

No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Ejercio de programaci贸n greedy: main code

38/42
Recursos

Vamos a replicar nuestro ejemplo de hace 2 clases programando nuestro main en donde:

  • Tenemos un cambio N de $27
  • Nuestras denominaciones coinSet son 1,5,10,15 y 20
  • Nos regrese cu谩ntas monedas dar de cambio

No olvides optimizar el c贸digo para mostrarnos c贸mo podr铆as imprimir las denominaciones de cada moneda entregada.

Aportes 65

Preguntas 1

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

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: 鈥淪ubestructura 贸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 鈥渕谩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 鈥渇unci贸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