Bien, este algoritmo es una tarea bastante común, cuando nuestro profesor de Algorítmica I nos lo dejo lo bautizamos como el "Algoritmo de las monedas". Consiste en crear un programa que reciba como parámetros:
*El numero de valores de monedas (Ej. 5)
*Los valores de las monedas (Ej. 1, 2, 5, 10, 20)
*La cantidad de monedas de cada valor (Ej. 20, 20, 10, 10, 10)
*Un monto de cambio. (Ej. 212)
El programa debe responder con una forma de dar ese monto de cambio usando el mínimo numero de monedas. Para el ejemplo seria:
Como ampliación al problema se considera que el programa pueda volver a dar otro cambio con las monedas restantes.
Yo use para resolver este problema una función recursiva, si alguien tiene otro algoritmo para resolver el mismo problema seria bueno que lo postee quisiera ver otras soluciones. Un amigo hizo un algoritmo iterativo pero era poco eficiente.
Aquí les va el código. Espero le sirva a alguien.
#include <iostream.h>
#include <conio.c>
bool monedas(int usa[30], int mon[30], int can[30], int index, int saldo, int n);
void main(){
//mon es un arreglo que contendra los valores de las monedas
//can es otro arreglo que tendra las cantidades de las monedas de cada valor
//usa, tendrá la cantidad de monedas usadas para cada valor
//estos arreglos deven relacionarse segun el indice es decir para un indice i en mon[i] esta el valor de una moneda,
// en can[i] la cantidad de monedas de ese valor y en usa[i] las monedas entregadas o ya usadas de ese valor.
int mon[30], can[30], usa[30]={0}, n, m;
int c, aux, op;
//solicita el numero de valores de monedas y lo valida
do{
clrscr();
cout<<"Ingrese el numero de tipos de monedas: ";cin>>n;
}while(n<1 || n>30);
//solicita los valores de las monedas y valida que no se repitan
for(int i=0; i<n; i++){
do{
cout<<"Ingrese el valor de moneda "<<i+1<<": ";cin>>mon[i];
c=0;
for(int j=0; j<i; j++){
if(mon[i]==mon[j]){c++;}
}
if(c>0){cout<<"ERROR. El valor ya ha sido ingresado!. Ingrese otro valor."<<endl;}
}while(mon[i]<=0 || c==1);
}
//solicita la cantidad de monedas de cada valor y valida también.
for(int i=0; i<n; i++){
do{
cout<<"Cuantas monedas de valor "<<mon[i]<<" tiene?: ";cin>>can[i];
if(can[i]<0){cout<<"ERROR. Cantidad no valida! Ingrese nuevamente."<<endl;}
}while(can[i]<0);
}
//hacemos un ordenamiento simultaneo de mon y de usa de modo que mon quede ordenado de forma descendente
// y que no se pierda la relacion de los indices
//este algoritmo es una modificacion del conocido "Metodo de la Burbuja" para hacerlo en menos lineas.
for(int i=0; i<n-1; i++){
if(mon[i]<mon[i+1]){
aux=mon[i]; mon[i]=mon[i+1]; mon[i+1]=aux;
aux=can[i]; can[i]=can[i+1]; can[i+1]=aux;
i=-1;
}
}
do{
//limpia el arreglo usa (iguala todos los elementos a 0)
for(int i=0; i<30; i++){usa[i]=0;}
//pide el monto de cambio
cout<<"Ingrese un monto de cambio: ";cin>>m;
//monedas(); es una funcion booleana que devuelve verdadero si es que es posible dar cambio y falso de lo contrario.
//tambien modifica los arreglos usa y can para indicar como se dio el cambio.
if(monedas(usa, mon, can, 0, m, n)){
cout<<"Es posible dar cambio de la siguente manera: "<<endl;
for(int i=0; i<n; i++){cout<<usa[i]<<" de "<<mon[i]<<endl;}
aux=0;
for(int i=0; i<n; i++){aux=aux+usa[i];}
cout<<"Se usaron "<<aux<<" monedas para dar el cambio"<<endl;
}
else{
cout<<"No es posible dar cambio."<<endl;
}
//menu para volver a dar cambio
do{
cout<<"[1] Volver a dar cambio con el resto de monedas."<<endl;
cout<<"[2] Terminar."<<endl;
cout<<"Ingrese una opcion: ";cin>>op;
}while(op<1 || op>2);
}while(op!=2);
}
//esta es la parte importante del programa y tal vez la mas dificil de entender.
/*
Explicación del algoritmo:
Puedo decir que este algoritmo es un algoritmo optimista. Pues empieza creyendo que podrá dar cambio entregando las monedas
con mas altos valores (para que sea el mínimo numero de monedas). Pero eso en la mayoría de casos no es posible, casi siempre
le va a pasar que le queda un saldo del cambio menor a la moneda de valor mas bajo. Entonces podría decir que no es posible dar
cambio pero hay algunos casos en que el problema se soluciona si cuando empezamos no damos valores tan altos sino otros mas
bajos. Para solucionar ese problema este algoritmo se autocorrige cuando no puede dar cambio retrocede la configuración de los
arreglos usa y can hasta la ultima moneda de valor alto entregada y a partir de ahí da cambio con moneda de valor mas bajo,
si aun asi no puede dar cambio vuelve a retroceder y así sucesivamente hasta que encuentre una configuracion correcta para dar
cambio o hasta que se da cuenta que no puede dar cambio (cuando trata de dar cambio usando las monedas de valor mas bajo y
aun asi no puede).
*/
bool monedas(int usa[30], int mon[30], int can[30], int index, int saldo, int n){
if(saldo>=mon[index] && can[index]>0){
saldo=saldo-mon[index];
usa[index]=usa[index]+1;
can[index]=can[index]-1;
if(saldo==0){return true;}
return monedas(usa, mon, can, index, saldo, n);
}
else{
if(index==n-1){
saldo=saldo+mon[index]*usa[index];
can[index]=can[index]+usa[index];
usa[index]=0;
while(usa[index]==0 && index!=0){index--;}
if(usa[index]==0){return false;}
saldo=saldo+mon[index];
can[index]=can[index]+1;
usa[index]=usa[index]-1;
}
return monedas(usa, mon, can, index+1, saldo, n);
}
}
Autor