Vamos a replicar nuestro ejemplo de hace 2 clases programando nuestro main en donde:
No olvides optimizar el código para mostrarnos cómo podrías imprimir las denominaciones de cada moneda entregada.
Gloriq Lopez
No comprendí la lógica de este algoritmo. Alguien tan amable que me lo pueda explicar
Andres David Peña Velandia
Me pasa lo mismo con varios de los vídeos del profesor Ricardo Celis
Wilson Alexander Caal Pacay
que parte no entendiste, ya sabes que es una Función recursiva?
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
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
Ejecucion.main()
!Ejecución Algoritmo Cambio Exacto
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)
Gabriel Suarez
Alejandro P
Excelente, muy comprensible.
Javier
Leandro Tenjo
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
Enrique Gálvez
Jesús Adrián Arroyo Ceja
Gabriel Obregón
📝main en el problema del cambio de monedas
🪙 Conjunto de monedas
int coinSet[] = {1, 5, 10, 15, 20};
➡️ Define las denominaciones disponibles
➡️ Se envían a greedyChange para probar combinaciones
📏 Número de elementos
int n = sizeof(coinSet) / sizeof(coinSet[0]);
📦 sizeof(coinSet) → tamaño total en bytes
🔹 sizeof(coinSet[0]) → tamaño de un elemento
✂️ División = cantidad de monedas distintas
🎯 Valor del cambio
int N = 27;
➡️ Es el monto total que queremos dar en monedas
➡️ greedyChange lo va reduciendo recursivamente
⚡ Llamada a la función recursiva
cout << "El mínimo de monedas para dar cambio es: "
<< greedyChange(coinSet, n, N);
🔹 Llama a greedyChange
🔹 Devuelve el mínimo número de monedas necesarias
🔹 Imprime el resultado en pantalla
✅ Finalización
return 0;
📌 Marca el final correcto del programa
🔗 Relación con el resto del código
Mijal Enzani
hola! si no reconoce el g++ q hago?
Massimo Di Berardino
¡Hola @myjal! podrías compartirnos el error o mensaje que te muestra al ejecutar el comando, para poder ayudarte mejor. También que consola estás utilizando, la consola de windows los comando funcionan diferente.
Moisés Manuel Morín Hevia
Correlo desde visual studio code o te recomiendo un IDE de C que se llama Dev C++ super fácil de compilar & ejecutar código de C
Victor Andres Barilin
Creo que puede entenderse mas simple con este codigo en python
coinSet = [50, 25, 10, 5, 1] def greedyCoin(amount): if (amount <= 0): return [] res = [] for coin in coinSet: while (amount >= coin): amount -= coin res.append(coin) return res print(greedyCoin(113)) print(greedyCoin(110)) print(greedyCoin(68))
Aranza Gutierrez Mora
En python
def greedyChange(coinSet, N): # Esta función asume que coinSet está ordenado de mayor a menor result = [] for coin in reversed(coinSet): while N >= coin: N -= coin result.append(coin) return result # Definimos el conjunto de monedas coinSet = [1,5,10,15,20] # Monto del cual queremos dar cambio N = 37 # Calculamos las monedas necesarias result = greedyChange(coinSet, N) print("Monedas usadas para dar el cambio:", result) ```def greedyChange(*coinSet*, *N*): # Esta función asume que coinSet está ordenado de mayor a menor result = \[] for coin in reversed(*coinSet*): while *N* >= coin: *N* -= coin result.append(coin) return result \# Definimos el conjunto de monedascoinSet = \[1,5,10,15,20] \# Monto del cual queremos dar cambioN = 37 \# Calculamos las monedas necesariasresult = greedyChange(coinSet, N) print("Monedas usadas para dar el cambio:", result)
Didier Stiven Niño Alba
Hola, Solución en bash:
# !/bin/bash # Script para devolver el minimo de monedas frente a un costo. rgx_number="^[1-9]{1,1}([0-9]?){0,9}$" # monedas=(1 5 10 20 50 100 500) monedas=( 1 5 10 15 20) cambio=() function minChange() { cantidad=$1 if [[ $cantidad -le 0 ]]; then return; fi i=$((i+1)) for coin in ${monedas[*]} do if [[ $coin -le $cantidad ]]; then cambio[$i]=$coin fi done cantidad=$((cantidad-cambio[$i])) minChange $cantidad } read -p "Ingrese el monto a evaluar: " monto if [[ $monto =~ $rgx_number ]]; then minChange $monto echo -e "\nLa cantidad minima de monedas para esta transaccion es: ${#cambio[*]}" echo -e "La monedas de cambio son: ${cambio[*]}\n" else echo "No es un entero positivo o es un string" fi
Nicolas Alpargatero
Por si quieren ver una solución sencilla en Python, pero sin recursividad.
Walter De Jesús Medina Puy
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)
Gabriel Ichcanziho Pérez Landa
Juan Sebastian Mesa
Hollman Andres Barbon Florez
Cordial Saludo Juan Sebastian
Revisé tu código y al ejecutarlo me genera esté mensaje, a lo cual no le he encontrado la solución para poderlo compilar, agradecería tus comentarios.
Slds. Hollman
José Martínez Santana
Reto
Usuario anónimo
User
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
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, []));
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; }```
