Problema del cambio de monedas

Problema del cambio de monedas

Este problema busca encontrar el mínimo número de monedas tales que entre ellas suman una determinada cantidad. Es un típo del problema de la mochíla -que ya veremos detalladamente en otro artículo-, y cuyas aplicaciones exceden el ámbito específico del cambio de dinero.

Los valores de las monedas de las que dispondremos en éste problemas se pueden representar mediante un conjunto o un array de valores enteros positivos ordenados de menor a mayor.

La resolución del problema consiste en: dada una cantidad entera mayor o igual que cero, encontrar un conjunto de monedas – con valor positivo o cero-, en donde cada incognita de la ecuación será el número de monedas de cada valor que se utilizan.

ecuacion que resuelve el problema del cambio de monedas

Una situación similara éste problema es el de las formas en el que se pueden lanzar cierto número de dardos para obtener una determinada puntuación. El objetivo es obtener ésta puntuación con el mínimo número de lanzamientos posible.

Existen diferentes formas en las que podemos abordar, mediante programación, la resolución de éste problema.

Una estrategia de resolución es mediante programación dinámica. Consiste en encontrar en forma ascendente las combinaciones de monedas de valores más pequeños cuya suma alcanzaría el umbral que buscamos.

El enfoque que utilizaremos en éste artículo es el algoritmo voraz o greedy. Estos tipos de algoritmos están basados en una estrategia de búsqueda en la cuál se sigue una heurística consistente en escoger la opción óptima en cada paso local hasta conseguir llegar a la solución general óptima.

Existe muchísima información en Internet que explica de una forma más profunda el funcionamiento de éste tipo de algoritmos. En la web de la universidad de granada, podemos encontrar información que nos puede ser útil a la hora de programar éstos algoritmos.

Para éste artículo, os dejaré el código que use durante mis estudios universitarios para resolver éste problema.

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

#include "lib_cron.h"

/*-------------------------------------------------------------------------*/
/*                        CABECERAS DE FUNCIONES                           */
/*-------------------------------------------------------------------------*/


int solucion (int usados [4], long int cambio);
int factible (int usados [4], long int cambio, int moneda);
int seleccion (int candidatos[2][4]);
void objetivo (int usados[4], int candidatos[2][4]);

/*-------------------------------------------------------------------------*/
/*                          PROGRAMA PRINCIPAL                             */
/*-------------------------------------------------------------------------*/

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

	int candidatos[2][4] = {100, 100, 100, 100, 25, 10, 5, 1};
		/* monedas de 1, 5, 10, 25 */
	int usados [4] = {0, 0, 0, 0};

	int precio;
	long int cambio, n, m, moneda, tmp;
	unsigned long int centesimas, j;
	ldiv_t segundo;
	double segundo2;
	struct time t1, t2;

	clrscr ();

	if (argc<2){
		printf ("\n Sintaxis: moneda <cantidad_insertada>.\n");
		exit (1);
	}
	else{
		precio = 253;
		n = atol (argv[1]);
		cambio = n - precio;
		while (cambio<0) {
			printf ("\nNo es suficiente, introduce m s monedas\n");
			scanf ("%d", &amp;n);
			cambio+=n;
		} /*del While*/
		if (cambio == 0){
			printf ("\nSu tabaco, gracias\n");
			exit (1);
		}
		/*tmp = cambio;*/
		cronostart(&amp;t1);
		/*for (i=1; i<300000; i++){
			cambio=tmp;
			usados[0]=usados[1]=usados[2]=usados[3]=0;
			candidatos[0][0]=candidatos[0][1]=candidatos[0][2]=candidatos[0][3]=100;*/
			while (!solucion (usados, cambio)){
				moneda = seleccion (candidatos);
				if (moneda == -1){
					printf ("\n\nNo hay cambio en la m quina");
					exit (1);
				}
				candidatos[0][moneda]--;

				if (factible (usados, cambio, candidatos[1][moneda]))
					usados[moneda]++;
			} /*del while*/
		/*}*/
		objetivo (usados, candidatos);
		cronostop (&amp;t2);
		printf ("\a");
		centesimas = cronodifcent (&amp;t1, &amp;t2);
		segundo = ldiv (centesimas, 100L);
		printf ("\n\nEl n£mero de cent‚simas es: %lu", centesimas);
		segundo2 = segundo.quot+segundo.rem*0.01;
		printf ("\nEl n£mero de segundos es: %.2lf", segundo2);
	} /*del else*/
	getch ();
	return 0;
} /* Del Main*/

/*-------------------------------------------------------------------------*/

int solucion (int usados[4], long int cambio){

	 return ((usados[0]*25 + usados[1]*10 + usados[2]*5 + usados[3]) == cambio);

} /*De la funci¢n soluci¢n */

/*-------------------------------------------------------------------------*/

int factible (int usados[4], long int cambio, int moneda){

	 return ((usados[0]*25 + usados[1]*10 + usados[2]*5 + usados[3]+moneda) <= cambio);

} /*De la funci¢n factible */

/*-------------------------------------------------------------------------*/

int seleccion (int candidatos[2][4]){

	int encontrado = 0;
	int i = 0;

	while (!encontrado &amp;&amp; (i < 4))
		if (candidatos[0][i] > 0){
			encontrado = 1;
			return (i);
		}
		else i++;
	return (-1);
}

/*-------------------------------------------------------------------------*/

void objetivo (int usados[4], int candidatos[2][4]){
	int i;

	printf("\nLa m quina devuelve:");
	for (i=0; i<4; i++)
		if (usados[i] != 0)
			printf ("\n%d monedas de %d", usados[i], candidatos[1][i]);
	printf ("\n\nSu tabaco. Gracias\n.");
}

Tengo otra versión de éste mismo algoritmo que os lo dejo a continuación, por si preferís utilizarla:

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

#include "lib_cron.h"

/*-------------------------------------------------------------------------*/
/*                          PROGRAMA PRINCIPAL                             */
/*-------------------------------------------------------------------------*/

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

	long int candidatos[3][4] = {100, 100, 100, 100, 25, 10, 5, 1, 0, 0, 0, 0};

	int precio;
	long int cambio, n;
	int i, cont;
	int nohay;
	div_t resultado;
	struct time t1, t2;
	ldiv_t segundo;
	double segundo2;
	unsigned long int centesimas, j;

	int tmp;

	clrscr ();

	if (argc<2){
		printf ("\n Sintaxis: Moneda2 <cantidad>.\n");
		exit (1);
	}
	else{
		precio = 253;
		n = atol (argv[1]);
		cambio = n - precio;
		while (cambio<0){
			printf ("\nNo es suficiente, introduce m s monedas\n");
			scanf ("%d", &amp;n);
			cambio+=n;
		} /*del While*/
		printf ("\nPrecio: %d\nCambio: %ld\n", precio, cambio);

		if (cambio == 0) {
			printf ("\nSu tabaco, gracias\n");
			exit (1);
		}
		/*tmp = cambio;*/
		cronostart (&amp;t1);
		/*for (j=0; j<300000; j++){
			cambio = tmp;
			candidatos[2][0]=candidatos[2][1]=candidatos[2][2]=candidatos[2][3]=0;*/
			i = 0;
			while ((cambio != 0) &amp;&amp; (i<4)){
				resultado = div (cambio, candidatos[1][i]);
				if (resultado.quot>0){
					nohay = resultado.quot - candidatos[0][i];
					if (nohay > 0){
						candidatos[2][i] = candidatos[0][i];
						candidatos[0][i] = 0;
					}
					else{
						candidatos[0][i]-= resultado.quot;
						candidatos[2][i]+= resultado.quot;
					}
					cambio-= candidatos[1][i]*candidatos[2][i];
				}
				i++;
			} /*del while*/
		/*}*/
		if (cambio != 0){
			printf ("\n\nNo hay suficiente cambio\n");
			exit (1);
		}
		printf ("\n\nLa m quina devuelve:\n\n");
		for (i=0; i<4; i++){
			if (candidatos[2][i] != 0)
				printf ("%ld monedas de %ld\n", candidatos[2][i], candidatos[1][i]);
		}

		cronostop (&amp;t2);
		printf ("\a");
		centesimas = cronodifcent (&amp;t1, &amp;t2);
		segundo = ldiv (centesimas, 100L);
		printf ("\n\nEl n£mero de cent‚simas es: %lu", centesimas);
		segundo2 = segundo.quot+segundo.rem*0.01;
		printf ("\nEl n£mero de segundos es: %.2lf", segundo2);
	}

	getch ();

	return (0);
}

Como siempre digo, estos sólo son dos propuestas. Os dejo a vuestra disposición la sección de comentarios de éste blog, o mis redes sociales, para que dejéis vuestras aportaciones.

No Comments

Deja un comentario

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.