Ejercicio de programación greedy

A lo largo del curso Me he sentido perdido en el COMO se desarrolla algoritmo de una forma lógica. Osea el por que y la secuencia de cada linea de código. Y siento que esto me pasa debido a en muchas ocasiones, llegado un punto el profe dice “espera, no te preocupes, mas adelante veras por que” Y eso hace (desde mi punto de vista) que a lo largo del desarrollo del código quede huecos que después con un repaso muy general no se cierran. y esto sin contar que el cambio de sintaxis de cada lenguaje si no es conocido ayuda en la confusión.
Y digo que pasa en el Código, por que cuando explica los conceptos, son muy claros y entendibles teóricamente el problema siento yo es al pasar al código.

No se si platzi tenga actualmente un curso de ciencias de la computación, en ciencias para la computación se hablan en mas detalle de:

• Cada uno de los métodos de ordenamiento para listas(Por lo menos con mas detalle).
• Temas de Matemáticas Discretas para optimización de algoritmos
  • En el caso de Conjuntos potencia y Teorema de Cantor
  • Complejidad algorítmica
  • Consumo en Memoria
• Grafos y Arboles
  • Cada uno de los tipos de arboles y su forma de uso
  • Teoria de Grafos
  • Arboles B
  • Arboles B+
  • Arboles Binarios Simples
  • Arboles AVL
  • Arboles Roji-negros
• Operaciones pre-orden y pos-orden para compiladores

sería bueno hacer los ejemplos con buenas prácticas de nomenclatura de variables y no poner nombres como: “res” o “n” y “N”

Lo desarrollé de la siguiente manera en Python:

import random

def greedychange(coins_set, change, coins):

    for i in range(len(coins_set)-1,-1,-1):
        if change == 0:
            return coins
        elif change >= coins_set[i]:
            coins.append(coins_set[i])
            return greedychange(coins_set, change - coins_set[i], coins)

if __name__ == '__main__':

    Cambio = random.randint(7, 30)

    print(f'Se requiere devolver {Cambio} pesos de cambio\n')
    monedas_denominaciones = [1 ,5, 10, 15]
    vueltos_en_monedas = []

    greedychange(monedas_denominaciones, Cambio, vueltos_en_monedas)
    print('Se entregaran las siguientes denominaciones: ', vueltos_en_monedas)```

En Bogotá se dice las vueltas, estas las guardaba para ahorralas y comprar libros de programación, no existía Internet 😃

Como bien dices Celis, en México se le dice “cambio”, en tiempos pasados era casi como “oro”, cuando era el resultado de ir por las tortillas y pasabas por un lugar de maquinitas (Arcades, videojuegos) 😄

En Venezuela 🇻🇪 se le dice vuelto!

En México, en algunas zonas es común decirle “feria”

Ay ! el lenguaje C no me cae tan bien, mejor Python que es un amor.

el cambio en colombia se dice Cambio vueltas de todo la verdad.

El Chile al cambio le llamamos vuelto, sería interesante en el ejercicio poder aplicar una ley nueva en mi pais llamada “ley del vuelto”, que sirve para redondear los vueltos ya que las monedas de 1 y 5 casi están fuera de circulación, por su nulo valor.

Me gustaría mucho que hicieran una escuela o una ruta de aprendizaje dedicada a entender el codigo del un SO para poder hacer aportes

Alguien que me ayude en este pregunta, si aun no conoces el lenguaje de programación en el que intentan explicarte un algoritmo, eso dificulta tu aprendizaje si o no? que piensan amigos?

En Mexico se dice, “cambio”, o “feria” xd

En El Salvador se dice “el vuelto” o " el cambio"

Vaya, estoy listo, por cierto, el código es arte.🤩

Aquí en México le solemos decir feria o morralla al cambio jaja

Mi intención con C es para aprender a programar videojuegos y además para programar Arduinos y Raspberry PI.

En República Dominicana se dice: Devuelta.

Si no fuera por GPT ya hubiera desertado🤣

Aportarian sin duda en el caso de la creación de un curso de C y C++, (deep functions) porque creo que son lenguajes que aportan mucho en la forma de programar actualmente. Ahorrarian el tiempo de leer un libro (lo cual me parece excesivamente positivo) para entender el lenguaje, y sería más visual en el aprendizaje.

A los que se sientan perdidos, sobre todo desde los algoritmos de ordenamiento, entiendo su dolor xp

Y bueno, no entendí:
*Por qué usa la función min
*Por qué usa la librería <climits>
*Qué es lo que retorna coins
*Cómo funciona el algoritmo (ahora en C++, sería el 4to lenguaje luego de c, java, python que han visto en un solo curso).

A los que se sientan perdidos, no se den por vencidos, es solo un reto mas para entender la computación y nadie dijo que seria super fácil. Aquí les dejo información relacionada a los algoritmos de ordenamiento para que lo chequen https://kesquivel.files.wordpress.com/2012/09/tema_1_algoritmosordenacionbusqueda1.pdf

cuando la maquina no tenga cambio te da chicles

aqui hya una explicacion de las librerias limits

https://www.tutorialspoint.com/c_standard_library/limits_h

en 🇨🇴 se dice “vueltas”

En españa tanto el cambio, como la vuelta se utiliza.

en python el int_max se puede hacer con float(‘inf’)

Me gustaría ver algoritmos como el de Dijkstra programado, o algo parecido apra encontrar el camino más corto. :9

En mi país es Vuelto, aquí en Colombia donde vivo actualmente es vueltas.

La verdad es que yo estoy en esta ruta de aprendizaje para aprender a programar desde cero, esto quiere decir que no cuento con muchas bases de programación, cuando se hacen los cambios a otro lenguaje se me dificulta y algunas funciones las desconozco, sobre todo el hecho de que extension usar o como compilar, he estado siguiendo la ruta de fundamentos de programación y solo he visto C y C++, a excepción del curso de programación básica donde vi JavaScript. El profesor si explica los conceptos muy bien, no tengo problema para que sirve cada algoritmo, pero donde empiezan mis problemas son en los códigos, literal, me llego a perder…

Me salta errores en el editos, pero esperemos que en la sguiente clase se solucionen

#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 el set de monedas
    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;
    
}```

La morralla

Un quinto le decimos en mi pueblo.

haaa con que asi era XD

En Bogotá se le dice devueltas.

Una forma de aplicar este algoritmo en C

En python:
![](

De_veinte = [20,20,20,20,20]
De_diez = [10,10,10,10,10]
De_cinco = [5,5,5,5,5]
De_uno = [1,1,1,1,1]

def respalda(arreglo) :
    vector = []
    for i in arreglo:
        vector.append(i)
    return vector

def Dame_moneda(cantidad) :
    cambio = []
    sincambio = False

    global De_veinte
    global De_diez
    global De_cinco
    global De_uno
    V = respalda(De_veinte)
    D = respalda(De_diez)
    C = respalda(De_cinco)
    U = respalda(De_uno)

    while cantidad:
        if cantidad >= 20 :
            if De_veinte != [] :
                cambio.append(20)
                De_veinte.pop()
                cantidad -= 20
                sincambio = False
                continue
            else :
                sincambio = True

        if cantidad >= 10 :
            if De_diez != [] :
                cambio.append(10)
                De_diez.pop()
                cantidad -= 10
                sincambio = False
                continue
            else :
                sincambio = True

        if cantidad >= 5 :
            if De_cinco != [] :
                cambio.append(5)
                De_cinco.pop()
                cantidad -= 5
                sincambio = False
                continue
            else :
                sincambio = True
        if cantidad >= 1 :
            if De_uno != [] :
                cambio.append(1)
                De_uno.pop()
                cantidad -= 1
                sincambio = False
                continue
            else :
                sincambio = True
        if sincambio :
            break
    if sincambio :
        De_veinte = V
        De_diez = D
        De_cinco = C
        De_uno = U
        return []
    else:
        return cambio


if __name__ == "__main__" :
    while (True) :
        try:
            cantidad = input("ingresa la cantidad que quieras retirar [salir]\n")
            if str(cantidad) == "salir" :
                break
            int (cantidad)
        except ValueError :
            print("el valor es incorrecto intenta de nuevo\n")
            continue
        else:
            cambio = Dame_moneda(int(cantidad))
            if cambio:
                print("tu cambio es : {} \n".format(cambio))
            else:
                print("lo sineto no hay suficiente cambio")

En C++ ok aqui se me complico por que por error al hacer remplase borre parte de la librería vector así que tuve que reconstruir la parte borrada pero al fina pude hacerla funcionar dándole mi propio toque XD
![](

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

template <typename T> deque<T> &operator<<(deque <T> &s,const T &valor){
    s.push_back(valor);
    return s;}

ostream &operator<<(ostream &o,const vector<int>&v){
    vector<int>::const_iterator i;
    o <<"[ ";
    for(i = v.begin(); i != v.end();++i)
        o<<*i<<" ";
    return o<<"]";}

deque<int> De_Veinte;
deque<int> De_Diez;
deque<int> De_Cinco;
deque<int> De_Uno;

vector<int> Dame_Cambio(const int &CANTIDAD){
    vector<int>Cambio;
    int cantidad = CANTIDAD;
    bool sinCambio = false;
    deque<int> V = De_Veinte;
    deque<int> D = De_Diez;
    deque<int> C = De_Cinco;
    deque<int> U = De_Uno;
    while(cantidad){
        if(cantidad >= 20){
            if(!De_Veinte.empty()){
                cantidad -= 20;
                Cambio.push_back(20);
                De_Veinte.pop_back();
                sinCambio = false;
                continue;}
           else
                sinCambio = true;}

        if(cantidad >= 10){
            if(!De_Diez.empty()){
                cantidad -= 10;
                Cambio.push_back(10);
                De_Diez.pop_back();
                sinCambio = false;
                continue;}
           else
                sinCambio = true;}

        if(cantidad >= 5){
            if(!De_Cinco.empty()){
                cantidad -= 5;
                Cambio.push_back(5);
                De_Cinco.pop_back();
                sinCambio = false;
                continue;}
           else
                sinCambio = true;}

        if(cantidad >= 1){
            if(!De_Uno.empty()){
                cantidad -= 1;
                Cambio.push_back(1);
                De_Uno.pop_back();
                sinCambio = false;
                continue;}
           else
                sinCambio = true;}

        if(sinCambio)
            break;}

    if(sinCambio){
        De_Veinte = V;
        De_Diez = D;
        De_Cinco = C;
        De_Uno = U;
        vector<int>vacio;
        return vacio;}
    else
        return Cambio;}

int main()
{
    De_Veinte<<20<<20<<20<<20<<20;
    De_Diez  <<10<<10<<10<<10<<10;
    De_Cinco <<5<<5<<5<<5<<5;
    De_Uno   <<1<<1<<1<<1<<1;
    while(true){
        int cantidad;
        cout<<"ingresa la cantidad que deseas retirar [-1 = salir]"<<endl;
        cin>> cantidad;
        vector<int>cambio;
        if(cantidad == -1)
            break;

        cambio = Dame_Cambio(cantidad);

        if(!cambio.empty())
            cout <<"tu cambio es : "<<cambio<<endl;
        else
            cout <<"lo sentimos no hay cambio suficiente"<<endl;}
    return 0;
}

Antes de ver el vídeo me aventé mi versión del greedy en mis tres lenguajes aquí el de C:
![](

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

void push_back(int **arreglo, int contenido);
void pop(int **arreglo);
void copiar(const int *Original,int **copia);
void imprimir(const int *vector);

typedef struct Dinero{
    int * veinte;
    int * diez;
    int * cinco;
    int * uno;       }Dinero;

Dinero *Billetes(int cantidad);
void Quemar_Dinero(Dinero *billetes);
Dinero * Respaldar(const Dinero* existente);

#define SI '\0'
#define NO '\1'

int *Dame_cambio(const int cantidad,Dinero **Cajero){
    char HayCambio = SI;
    int *Cambio = NULL;
    Dinero *Bolsa = Respaldar(Cajero[0]);
    int Restante = cantidad;
    while(Restante){
        if(Restante >= 20){
            if(Cajero[0]->veinte){
                pop(&Cajero[0]->veinte);
                push_back(&Cambio,20);
                Restante -= 20;
                HayCambio = SI;
                continue;}
            else
                HayCambio = NO;}

        if(Restante >= 10){
            if(Cajero[0]->diez){
                pop(&Cajero[0]->diez);
                push_back(&Cambio,10);
                Restante -= 10;
                HayCambio = SI;
                continue;}
            else
                HayCambio = NO;}

        if(Restante >= 5){
            if(Cajero[0]->cinco){
                pop(&Cajero[0]->cinco);
                push_back(&Cambio,5);
                Restante -= 5;
                HayCambio = SI;
                continue;}
            else
                HayCambio = NO;}

        if(Restante >= 1){
            if(Cajero[0]->uno){
                pop(&Cajero[0]->uno);
                push_back(&Cambio,1);
                Restante -= 1;
                HayCambio = SI;
                continue;}
            else
                HayCambio = NO;}
        if(HayCambio)
            break;}

    if(HayCambio){
        Quemar_Dinero(Cajero[0]);
        Cajero[0] = Bolsa;
        if(Cambio)
            free(Cambio);
        return NULL;}
    else{
        Quemar_Dinero(Bolsa);
        return Cambio;}}

int main()
{
    Dinero *cajero = Billetes(5);
    int * Cambio = NULL;
    while(1){
        int cantidad;
        printf("Cuanto deseas retirar [-1 = salir]\n");
        scanf("%d",&cantidad);

        if(cantidad == -1) break;

        Cambio = Dame_cambio(cantidad,&cajero);
        imprimir(Cambio);
        free(Cambio);
        Cambio = NULL;}

    Quemar_Dinero(cajero);
    return 0;
}

void push_back(int **arreglo, int contenido){
    if(arreglo == NULL)return;
    if(arreglo[0]== NULL){
        arreglo[0] = (int *)calloc(2,sizeof(int));
        arreglo[0][0] = 2;
        arreglo[0][1] = contenido;
        return;}
    int dimencion = arreglo[0][0];
    int *Nuevo_arreglo = (int*)calloc(dimencion + 1,sizeof(int));
    Nuevo_arreglo[0] = dimencion + 1;

    int i;
    for(i = 1; i < dimencion;++i)
        Nuevo_arreglo[i] = arreglo[0][i];

    Nuevo_arreglo[dimencion] =contenido;
    free(arreglo[0]);
    arreglo[0]= Nuevo_arreglo;}

void pop(int **arreglo){
    if(arreglo == NULL||arreglo[0]==NULL)return;
    int dimencion = arreglo[0][0] - 1;

    if(dimencion == 1){
        free(arreglo[0]);
        arreglo[0] = NULL;
        return;}

    int *Nuevo_arreglo = (int*)calloc(dimencion,sizeof(int));
    Nuevo_arreglo[0] = dimencion;
    int i;
    for(i = 1; i < dimencion;++i)
        Nuevo_arreglo[i] = arreglo[0][i];
    free(arreglo[0]);
    arreglo[0] = Nuevo_arreglo;}

void copiar(const int *Original,int **copia){
    if(Original == NULL){
        copia[0] = NULL;
        return;}
    if(copia||copia[0]) free(copia[0]);
    copia[0] = (int *)calloc(Original[0],sizeof(int));
    int i;
    for(i = 0; i < Original[0];++i)
        copia[0][i] = Original[i];}

void imprimir(const int *vector){
    if(vector == NULL){
        printf("Lo sentimos no hay suficiente cambio\n");
        return;}
    int i;
    printf("Su cambio : [ ");
    for(i = 1; i < vector[0]; ++i)
        printf("%d ",vector[i]);
    printf("]\n");}

Dinero *Billetes(int cantidad){
    Dinero *Bolsa = (Dinero*)malloc(sizeof(Dinero));
    Bolsa->veinte = (int*)calloc(cantidad + 1,sizeof(int));
    Bolsa->diez = (int*)calloc(cantidad + 1,sizeof(int));
    Bolsa->cinco = (int*)calloc(cantidad + 1,sizeof(int));
    Bolsa->uno = (int*)calloc(cantidad + 1,sizeof(int));

    Bolsa->veinte[0] = cantidad + 1;
    Bolsa->diez[0] = cantidad + 1;
    Bolsa->cinco[0] = cantidad + 1;
    Bolsa->uno[0] = cantidad + 1;

    int i;
    for(i = 1; i <= cantidad;++i){
        Bolsa->veinte[i] = 20;
        Bolsa->diez[i] = 10;
        Bolsa->cinco[i] = 5;
        Bolsa->uno[i] = 1;}
    return Bolsa;}

void Quemar_Dinero(Dinero *billetes){
    if(billetes == NULL)return;
    if(billetes->veinte)free(billetes->veinte);
    if(billetes->diez)free(billetes->diez);
    if(billetes->cinco)free(billetes->cinco);
    if(billetes->uno)free(billetes->uno);
    free(billetes);}

Dinero *Respaldar(const Dinero* existente){
    if(existente == NULL)return NULL;
    Dinero *respaldo = (Dinero*)malloc(sizeof(Dinero));
    copiar(existente->veinte,&respaldo->veinte);
    copiar(existente->diez,&respaldo->diez);
    copiar(existente->cinco,&respaldo->cinco);
    copiar(existente->uno,&respaldo->uno);
    return respaldo;}```

Es muy lenta la complementación recursiva hecha.

Mi código adaptado a 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 = 30;
            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;
        }
    }
    
}

Me emociona mucho hacer codigo en las clases:

#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(coin, res+1);
    }
  }
  return coins;
}

Cómo soporte y profundización para este curso recomiendo:
Introduction to Algorithms. Thomas H. Cormen et Al.
No se imaginan cuanta información tiene, ejercisios y de todo. Ojalá les sea de ayuda.

Hola Amigos,

No entiendo aun para que se usa la N y la n, creo que la n es la longitud del arreglo coinSet, pero la N no la entiendo

Me pueden ayudar por favor?

Mil gracias

Feria jajajaja

Para usarlo en Robótica

En JavaScript!

function greedy(coinsSet, change, coins){
    for(let item of coinsSet){
        if(change === 0){
            return coins 
        } else if(item <= change){
            coins.push(item)
            return greedy(coinsSet, change - item, coins)
        }
    }
}

const coinsSet = new Set([100000,50000,20000,10000,5000,2000,1000,500,200,100])
const change = (Math.floor(Math.random() * (5000 - 10)) + 10) * 100
const coins = []

greedy(coinsSet, change, coins)

¿Hay que tener un Arduino para tomar el curso de Fundamentos de Desarrollo de Hardware con Arduino?