Autor
Se tiene un conjunto de N tipos de monedas, cada una con un valor xi. Se supone que contamos con una cantidad ilimitada de monedas de cada tipo. El problema consiste en hallar el número mínimo de monedas que necesitamos para dar una cierta cantidad C.
Hay que tener en cuenta que un algoritmo voraz que eligiese siempre la moneda de mayor valor que se pueda tomar para acercarse a la cantidad C no funcionaría para cualquier conjunto de tipos de monedas. Por ejemplo, si tenemos monedas de valores 1, 6 y 10, y la cantidad a completar fuera 24, la estrategia voraz elegiría las siguientes monedas: 10, 10, 1, 1, 1 y 1. Es decir se darían 6 monedas, cuando es posible devolver esa cantidad con solo 4 monedas de valor 6.
Respuestas a los siguientes apartados:
1. Describa el esquema algorítmico utilizado y como se aplica al problema, incluyendo las ecuaciones que representan el problema, y la tabla de resultados parciales.
2. Analice el coste computacional del algoritmo.
3. Exponga alternativas al esquema utilizado si las hay, y compare su coste con el de la solución realizada.
4. Describa los datos de prueba utilizados y los resultados obtenidos con ellos.
2.2.- Argumentos y parámetros La práctica se invoca usando la siguiente sintaxis:
cambio [-t][-h] [fichero_entrada] [fichero_salida]
Los argumentos son los siguientes:
-t: traza cada paso de manera que se describa la aplicación del algoritmo utilizado.
-h: muestra una ayuda y la sintaxis del comando.
fichero_entrada: es el nombre del fichero del que se leen los datos del sistema monetario: número de tipos de monedas y sus valores y la cantidad que se desea devolver.
fichero_salida: es el nombre del fichero que se creará para almacenar la salida. Si el fichero ya existe, el comando dará un error. Si falta este argumento, el programa muestra el resultado por pantalla.
2.3- Datos de entrada
El fichero de datos de entrada consta de:
Una primera línea que indica la cantidad que se desea devolver, C.
Una segunda línea que indica el valor de N que es el número de tipos de moneda del sistema monetario.
N líneas con un valor cada una que expresa el valor de una moneda. Estas líneas estarán ordenadas de forma creciente.
La entrada termina cuando se llega al final del fichero.
Por ejemplo, supongamos que se desea devolver la cantidad C=24, que el sistema monetario dispone de 3 tipos de moneda y sus valores son 1, 6 y 10. El fichero de entrada contendría:
24
3
1
6
10
2.4- Datos de salida
La salida es una secuencia de líneas indicando en cada línea la cantidad de cada tipo de moneda que hay que utilizar, solo si dicha cantidad es distinta de 0.
En el ejemplo, la salida sería:
4 monedas de 6
import java.io.*;
import java.util.ArrayList;
import java.util.Scanner;
public class cambio
{
private static boolean t = false;
private static boolean h = false;
private static String fichero_entrada = null;
private static String fichero_salida = null;
private int[][] matrizCambio;
private int[] vectorMonedas;
private int cantidad;
private int[] vectorSeleccion;
public cambio(int i, int[] js) {
// TODO Auto-generated constructor stub
}
public static void main(String[] args){
//Argumentos de prueba - Borrar
//args = new String [] {"-t","-h", "fichero_entrada","fichero_salida"};
if(args.length<=1){
for(int i=0;i<args.length;i++){
if(args.equals("-h")){
h = true;
}
else if(args.equals("-t")){
t = true;
}
else if(fichero_entrada == null){
fichero_entrada = args;
}
else{
fichero_salida = args;
}
}
if(h){
System.out.println("----------------------------- AYUDA --------------------------------");
System.out.println("cambio [-t][-h] [<fichero_entrada>][<fichero_salida>]");
System.out.println(" -t: Traza cada paso del algoritmo y describe utilización del algoritmo");
System.out.println(" -h: Muestra una ayuda y la sintaxis del comando");
System.out.println(" fichero_entrada: Se leen los datos del S.M No. de tipo de monedas y la cantidad que se desea devolver");
System.out.println(" fichero_salida: Almacena la salida, si el fichero ya existe el comando dara un error");
System.out.println("----------------------------------------------------------------------------------------------------------");
}
if(fichero_entrada != null){
ArrayList<String> lista=leerFichero(fichero_entrada);
// if(tieneSolucion(lista)){
String resultado = calcularCambio(lista);
if(fichero_salida !=null){
guardarSolucion(fichero_salida, resultado);
}
System.out.println("Resultado: " + resultado);
// }
// else{
// System.ot.println("No tiene solucion");
//
// }
}else{
System.out.println("Faltan argumentos");
}
}
}
private static String calcularCambio(ArrayList<String> lista) {
// TODO Auto-generated method stub
return null;
}
private static ArrayList<String> leerFichero(String rutaFichero){
ArrayList<String>lista=new ArrayList<String>();
try {
Scanner s=new Scanner(new File(rutaFichero));
while (s.hasNext()){
lista.add(s.next());
}
s.close();
}catch (FileNotFoundException e) {
System.out.println(e);
}
return lista;
}
/**
* Metodo con el que guardamos la solucion en el fichero de salida
*
* @param String filename, con el que indicamos el nombre del nuevo sifhero de salida.
* @param ArrayList<Integer> lista, con los valores que vamos a guardar en el fichero.
* */
private static void guardarSolucion(String filename, String resultado) {
BufferedWriter bufferedWriter = null;
//Crea un nuevo bufferedWritter y comprueba si hay excepciones
try {
bufferedWriter = new BufferedWriter(new FileWriter(filename));
bufferedWriter.write("resultado: "+ resultado);
} catch (FileNotFoundException ex) {
ex.printStackTrace();
} catch (IOException ex) {
ex.printStackTrace();
}
finally {
//Cierra el bufferedWritter
try {
if (bufferedWriter != null) {
bufferedWriter.flush();
bufferedWriter.close();
}
} catch (IOException ex) {
ex.printStackTrace();
}
}
}
void Cambio(int cantidad, int[] monedas){
this.cantidad = cantidad;
this.vectorMonedas = monedas;
matrizCambio = calcularMonedas(cantidad, monedas);
vectorSeleccion = seleccionarMonedas(cantidad, monedas, matrizCambio);
}
public int[] getVectorSeleccion(){
return this.vectorSeleccion;
}
private int[][] calcularMonedas(int cantidad, int[] monedas){
int[][] matrizCambio = new int[monedas.length + 1][cantidad + 1];
for (int i = 0; i < monedas.length; i++)
matrizCambio
- = 0;
for (int j = 1; j <= cantidad; j++)
matrizCambio[0][j] = 99;
for (int i = 1; i <= monedas.length; i++)
for (int j = 1; j <= cantidad; j++) {
if (j < monedas[i - 1]) {
matrizCambio[j] = matrizCambio[i - 1][j];
} else {
int minimo = 0;
minimo = min(matrizCambio[i - 1][j] , matrizCambio[j- monedas[i - 1]] + 1);
matrizCambio[j] = minimo;
}
cambio c = new cambio(24, new int[]{1,6,10});
c.getVectorSeleccion();
}
return matrizCambio;
}
private int[] seleccionarMonedas(int c, int[] monedas, int[][]tabla ){
int i,j;
int[] seleccion = new int[monedas.length];
for(i = 0; i< monedas.length; i++){ seleccion=0; } i= monedas.length; j= c; while(j>0){
if(i>1 && tabla[j]==tabla[i-1][j]){
i--;
}
else{
seleccion[i-1]++;
j = j - monedas[i-1];
}
}
return seleccion;
}
private int min(int a, int b){
if(a<b)
return a;
else
return b;
}
}
En línea
