Ejercicio Java: Dando cambio en el autobús

Ejercicio tomado de: Primer Concurso Local de Programación ACM ICPC - Universidad Autónoma Metropolitana Unidad Azcapotzalco.

Este es un ejemplo en el cual podemos hacer uso de vectores.

Dando cambio en el autobús

Si los conductores de autobús hicieran bien su trabajo (y no nos referimos al buen conducir, para lo cual hay poca esperanza) debieran de dar el cambio usando tan pocas monedas como sea posible. Así no molestarían a los clientes ni se les acabarían las monedas. En nuestro país tenemos monedas de 1, 2, 5, 10 y 20 pesos, así que si quisieramos dar 47 pesos de cambio, lo mejor que podemos hacer es dar dos monedas de 20, una de 5 y una de 2. Sin embargo, en algún otro país podrían tener otros valores para las monedas, como por ejemplo de 1, 3 y 5. Escriba un programa que, dados la cantidad c de cambio a dar, la cantidad m de monedas distintas de las que se dispone, y los valores v1,...,vm de esas monedas  encuentre una forma de dar el cambio usando tan pocas monedas como le sea posible. Suponga que siempre habrá monedas de valor 1, así que siempre se puede dar cualquier cantidad de cambio.

Entrada: 1 ≤ m ≤ 100 y 1 = v1 < v2 < ... < vm ≤ c ≤ 1000.

SOLUCIÓN

package ejeBus;

import java.util.Scanner;

public class aplic {

public static void main(String[] args){
int c,n;
Scanner leer= new Scanner(System.in);
System.out.println("Ingrese cantidad de cambio:");
c=leer.nextInt();
//validamos con un do-while la cantidad de monedas
do {
System.out.println("Ingrese cantidad de monedas:");
n=leer.nextInt();
} while (n<0 || n>100);
//creamos un vector para nuestras monedas y otro que alamacenará la cantidad de monedas
int[] vec=new int[n];
int[] mon=new int[n];
//leemos las monedas validando que estén entre el rango que nos piden
for (int i = 1; i < vec.length; i++) {
int z=i+1;
do {
System.out.print("Ingrese valor de moneda ["+z+"] :\t");
vec[i]=leer.nextInt();
System.out.println();
} while (vec[i]<0 || vec[i]>1000);

}
//asignamos a la posición 0 el valor de uno, por que dice que todos el conjunto de monedas
//debe contar con una de valor uno
vec[0]=1;
//utilizamos un método de ordenamiento para poder comparar más rápido
//a las monedas de más valor
for (int i = 0; i < vec.length; i++) {
for (int j = 0; j < vec.length; j++) {
if (vec[i]>vec[j]) {
int op=vec[i];
vec[i]=vec[j];
vec[j]=op;
}
}
}
//CON UN FOR RESOLVEMOS EL EJERCICIO
for (int i = 0; i < mon.length; i++) {
//EN ESTE WHILE VALIDAREMOS QUE SE RESTE MONEDA POR MONEDA
while (c>=vec[i]) {
c=c-vec[i];
mon[i]++;
}
}
//FINALMENTE MOSTRAMOS LA SOLUCIÓN
System.out.print("Monedas ");
for (int i = 0; i < vec.length; i++) {
System.out.print("\t"+vec[i]);
}
System.out.println("");
System.out.print("Cantidad");
for (int i = 0; i < mon.length; i++) {
System.out.print("\t"+mon[i]);
}
}

}