Algoritmos de Esquemas en Java: Voraz, Vuelta Atrás, Grafos y Backtracking

Esquemas algorítmicos en Java

A continuación se presentan los ejercicios de esquemas algorítmicos implementados en Java, organizados por técnica: algoritmos voraces, vuelta atrás (backtracking) y grafos.

Ejercicio 1: Dar el cambio voraz

public class Esquemas {

// Ejercicio 1: Dar el cambio voraz

public static Map darCambio(int importeDevolver, Map cantidades) {

Map solucion = new HashMap<>();

int importeDevuelto = 0;
boolean devolverMas = true;
while (importeDevuelto < importeDevolver && devolverMas) {

Integer billeteSel = mayor(importeDevolver - importeDevuelto, cantidades);
if (billeteSel != 0) {

int cantBil = (importeDevolver - importeDevuelto) / billeteSel;

int tot = cantidades.get(billeteSel);
if (cantBil > tot) cantBil = tot;
solucion.insertar(billeteSel, cantBil);
importeDevuelto += billeteSel * cantBil;
if (tot - cantBil == 0) cantidades.eliminar(billeteSel);
else cantidades.insertar(billeteSel, tot - cantBil);
} else devolverMas = false; // No se puede devolver

}

if (devolverMas == false) return new HashMap<>();
else return solucion;
}

private static Integer mayor(int importeQueda, Map cant) {
Integer billMax = 0;
Iterator it_bill = cant.getClaves();

while (it_bill.hasNext()) {
Integer bill = it_bill.next();

if (bill > billMax && bill <= importeQueda && cant.get(bill) > 0) {
billMax = bill;
}
}
return billMax;
}

// Ejercicio 2: Dar el cambio vuelta atrás

public static boolean darCambio(int importeDevolver, Map cantidades, Map solucion) {

boolean objetivo = false;
Iterator it_bill = cantidades.getClaves();

while (it_bill.hasNext() && !objetivo) {
int moneda = it_bill.next();

if (cantidades.get(moneda) > 0 && importeDevolver >= moneda) {
cantidades.insertar(moneda, cantidades.get(moneda) - 1);
if (moneda == importeDevolver) {
solucion.insertar(moneda, solucion.get(moneda) + 1);
objetivo = true;
} else {
objetivo = darCambio(importeDevolver - moneda, cantidades, solucion);
if (objetivo)
solucion.insertar(moneda, solucion.get(moneda) + 1);
else {
cantidades.insertar(moneda, cantidades.get(moneda) + 1);
}
}
}
}
return objetivo;
}

Ejercicio 3: Grabar CD voraz

// Ejercicio 3: Grabar CD voraz
public static Lista llenarCDVoraz(int capacidadMaxima, Map espacioProgramas) {

Lista CD = new ListaEnlazada();
int espacioOcupado = 0;
boolean llenarMas = true;

int k = 0;
while (espacioOcupado < capacidadMaxima && llenarMas) {

String prog = mayor(capacidadMaxima - espacioOcupado, espacioProgramas, CD);
if (prog != null) {
k = espacioProgramas.get(prog);
espacioProgramas.eliminar(prog);
CD.insertarPrincipio(prog);
espacioOcupado += k;
} else llenarMas = false;
}

return CD;
}

private static String mayor(int parcial, Map progr, Lista sol) {
String maxProg = null;
int maxEsp = 0;

Iterator it_prog = progr.getClaves();

while (it_prog.hasNext()) {
String prog = it_prog.next();
int esp = progr.get(prog);

if (!sol.contiene(prog) && esp > maxEsp && esp <= parcial) {
maxEsp = esp;
maxProg = prog;
}
}

return maxProg;
}

Ejercicio 4: Grabar CD vuelta atrás

// Ejercicio 4: Grabar CD vuelta atrás
public static boolean llenarCDVueltaAtras(int capacidadCD, Map programas, Lista CD) {

boolean objetivo = false;
Iterator itProgramas = programas.getClaves();

while (itProgramas.hasNext() && !objetivo) {
String program = itProgramas.next();
int capacProgram = programas.get(program);

if (capacProgram > 0 && capacidadCD >= capacProgram) {
programas.eliminar(program);
if (capacProgram == capacidadCD) {
CD.insertarPrincipio(program);
objetivo = true;
} else {
objetivo = llenarCDVueltaAtras(capacidadCD - capacProgram, programas, CD);
if (objetivo)
CD.insertarPrincipio(program);
else {
programas.insertar(program, capacProgram);
}
}
}
}
return objetivo;
}

Ejercicio 5: Llenar mochila voraz

// Ejercicio 5: Llenar mochila

public static Map llenarMochila(int volumenMaximo, Map cantidades, Map volumenes) {

Map S = new HashMap<>();
int volumenOcupado = 0;
boolean llenarMas = true;

int cantObj = 0;
while (volumenOcupado < volumenMaximo && llenarMas) {
String obj = mayor(volumenMaximo - volumenOcupado, cantidades, volumenes);
if (obj != null) {
int vol = volumenes.get(obj);
cantObj = (volumenMaximo - volumenOcupado) / vol;
int tot = cantidades.get(obj);
if (cantObj > tot) cantObj = tot;

S.insertar(obj, cantObj);
if (tot - cantObj == 0) cantidades.eliminar(obj);
else cantidades.insertar(obj, tot - cantObj);

volumenOcupado += vol * cantObj;
} else llenarMas = false; // No se puede llenar más, devolvemos la mochila
}

return S;
}

private static String mayor(int parcial, Map c, Map v) {
String max = null;
int maxV = 0;

Iterator obj = v.getClaves();

while (obj.hasNext()) {
String m = obj.next();
int vol = v.get(m);
int cant = c.get(m);

if (cant > 0 && vol > maxV && vol <= parcial) {
maxV = vol;
max = m;
}
}

return max;
}

Ejercicio 6: Llenar mochila con restricción de volumen y peso

// Ejercicio 6: Llenar mochila, restricción de volumen y peso

public static Map llenarMochila(int volumenMaximo, int pesoMaximo, Map cantidades, Map volumenes, Map pesos) {

Map solucion = new HashMap<>();

int volumenOcupado = 0;
int pesoOcupado = 0;
boolean llenarMas = true;

// Mientras no se haya cumplido el objetivo con los objetos disponibles
while (volumenOcupado < volumenMaximo && llenarMas) {
// buscar un objeto que quepa
String obj = mayor(volumenMaximo - volumenOcupado, pesoMaximo - pesoOcupado, volumenes, cantidades, pesos);
if (obj != null) {
int vol = volumenes.get(obj);
int pes = pesos.get(obj);

int cantObj = (volumenMaximo - volumenOcupado) / vol; // ¿Cuántos objetos según volumen?
int s = (pesoMaximo - pesoOcupado) / pes; // ¿Cuántos objetos según peso?

if (cantObj > s) cantObj = s; // Me quedo con la cantidad más pequeña

int tot = cantidades.get(obj); // ¿Cuántos objetos tengo realmente?
if (cantObj > tot) cantObj = tot;

solucion.insertar(obj, cantObj);

if (tot - cantObj == 0) cantidades.eliminar(obj);
else cantidades.insertar(obj, tot - cantObj);

volumenOcupado += vol * cantObj;
pesoOcupado += pes * cantObj;
} else llenarMas = false; // No se puede llenar más, devolvemos la mochila
}

return solucion;
}

private static String mayor(int parcialVolumen, int parcialPeso, Map v, Map c, Map p) {
String max = null;
int maxV = 0;

Iterator obj = v.getClaves();

while (obj.hasNext()) {
String m = obj.next();
int vol = v.get(m);
int pes = p.get(m);

if (c.get(m) > 0 && vol > maxV && vol <= parcialVolumen && pes <= parcialPeso) {
maxV = vol;
max = m;
}
}

return max;
}

// El grafo debe estar bien construido, si no es posible que queden ciudades sin visitar

Ejercicio 7: Viajante (ciudades)

public static Grafo viajante(Grafo g, Vertice v) {
Vertice nodoActual = v;
Lista<Vertice> porVisitar = new ListaEnlazada<>();
Grafo solucion = new ListaAdyacencia<>();

Iterator<Vertice> it_v = g.vertices();

while (it_v.hasNext()) {
Vertice vert = it_v.next();
porVisitar.insertarPrincipio(vert);
}

porVisitar.suprimir(nodoActual);

boolean continuar = true;

while (!porVisitar.esVacio() && continuar) {
Arco u = minimo(g.arcos(), nodoActual, porVisitar);
if (u != null) {
porVisitar.suprimir(u.getDestino());
solucion.insertarArco(u);
nodoActual = u.getDestino();
} else continuar = false;
}
return solucion;
}

private static Arco minimo(Iterator<Arco> arc, Vertice v, Lista<Vertice> iPorVisitar) {
int dist_v_min = 0;
int min = Integer.MAX_VALUE;
Arco arco_min = null;
while (arc.hasNext()) {
Arco a1 = arc.next();
Vertice w = a1.getDestino();
if (a1.getOrigen().equals(v) && iPorVisitar.contiene(w)) {
dist_v_min = a1.getEtiqueta();
if (dist_v_min < min) {
arco_min = a1;
min = dist_v_min;
}
}
}
return arco_min;
}

Ejercicio 8: Algoritmo de Prim

public static Grafo prim(Grafo g, Vertice v) {
Lista<Vertice> porVisitar = new ListaEnlazada<>();
Lista<Vertice> visitados = new ListaEnlazada<>();
Grafo solucion = new ListaAdyacencia<>();

Iterator<Vertice> it_v = g.vertices();

while (it_v.hasNext()) {
Vertice vert = it_v.next();
porVisitar.insertarPrincipio(vert);
}

porVisitar.suprimir(v);
visitados.insertarPrincipio(v);

while (!porVisitar.esVacio()) {
Arco u = minimo(g.arcos(), porVisitar, visitados);
Vertice w = u.getDestino();
porVisitar.suprimir(w);
visitados.insertarPrincipio(w);
solucion.insertarArco(u);
}
return solucion;
}

private static Arco minimo(Iterator<Arco> arc, Lista<Vertice> iPorVisitar, Lista<Vertice> iVisitados) {
int dist_v_min = 0;
int min = Integer.MAX_VALUE;
Arco arco_min = null;

while (arc.hasNext()) {
Arco a1 = arc.next();
Vertice w = a1.getDestino();
Vertice v = a1.getOrigen();

if (iPorVisitar.contiene(w) && iVisitados.contiene(v)) {
dist_v_min = a1.getEtiqueta();
if (dist_v_min < min) {
arco_min = a1;
min = dist_v_min;
}
}
}
return arco_min;
}

Ejercicio 9: 8 reinas

// Ejercicio 9: 8 reinas

private static boolean buenSitio(int j, int[] tabl) {
// ¿Es amenaza colocar la reina j en A[j], con las anteriores?
int i;
for (i = 0; i < j; ++i) {
if (tabl[i] == tabl[j]) return false;
if (Math.abs(i - j) == Math.abs(tabl[i] - tabl[j])) return false;
}
return true;
}

public static boolean colocarReinas(int reina, int[] tablero) {
boolean objetivo = false;
int columna = 0;

// Mientras no se hayan mirado todas las posibilidades o alcanzado el objetivo
while (columna < 8 && !objetivo) {
// Colocar la reina j en la columna
tablero[reina] = columna;
if (buenSitio(reina, tablero)) {
// Si he colocado todas las reinas
if (reina == 7) {
objetivo = true;
} else {
// Hacer el siguiente paso recursivamente (colocar la siguiente reina)
if (colocarReinas(reina + 1, tablero)) {
objetivo = true;
} else {
tablero[reina] = -1; // vuelta atrás
}
}
}
columna++;
}

return objetivo;
}

Ejercicio 10: Laberinto

// Ejercicio 10: Laberinto

public static boolean ensayar(char[][] laberinto, int posicionX, int posicionY) {

int n = laberinto.length; // Tamaño del laberinto n x n
boolean toret;
// ¿Estamos dentro del laberinto?
if ((posicionX < 0) || (posicionX > n - 1) || (posicionY < 0) || (posicionY > n - 1))
toret = false;
else {
// No se puede pasar por encima de los obstáculos
if (laberinto[posicionX][posicionY] != ' ') {
toret = false;
} else {
// Marca como parte del camino
laberinto[posicionX][posicionY] = 'C';

if ((posicionX == n - 1) && (posicionY == n - 1)) {
toret = true; // Se ha encontrado la solución
} else {
// En principio, hay solución
toret = true;

// Hay que desplazarse en vertical u horizontal por las otras casillas
if (!ensayar(laberinto, posicionX + 1, posicionY))
if (!ensayar(laberinto, posicionX, posicionY + 1))
if (!ensayar(laberinto, posicionX - 1, posicionY))
if (!ensayar(laberinto, posicionX, posicionY - 1)) {
laberinto[posicionX][posicionY] = 'I';
toret = false;
}
}
}
}

return toret;
}

Ejercicio 11: Subconjuntos

// Ejercicio 11: subconjunto
public static boolean subconjuntos(int[] valores, int[] solucion, int suma, int i) {
boolean objetivo = false;
while (i < valores.length && !objetivo) {
int candidato = valores[i];
if (candidato <= suma) {
solucion[i] = 1;
if (candidato == suma) {
solucion[i] = 1;
objetivo = true;
} else {
objetivo = subconjuntos(valores, solucion, suma - candidato, i + 1);
if (!objetivo)
solucion[i] = 0; // vuelta atrás
}
}
i++;
}
return objetivo;
}

Ejercicio 12: k-ésimo menor elemento

// Ejercicio 12: k-ésimo menor elemento

// Selecciona un elemento pivote; entre dos elementos diferentes devuelve el elemento mayor
private static int buscaPivote(int i, int j, int[] array) {
int primer = array[i];
int k = i + 1;

while (k <= j) {
if (array[k] > primer)
return k;
else if (array[k] < primer)
return i;
else k++;
}
// Si llega al final del array y todos los elementos son iguales
return -1;
}

// Divide el array en menores que pivote, y mayores o iguales a pivote.
// Devuelve la posición del primer elemento de los mayores.
private static int particion(int i, int j, int pivote, int[] array) {
int derecha = i;
int izquierda = j - 1;
while (derecha <= izquierda) {
intercambiar(derecha, izquierda, array);

while (array[derecha] < pivote)
derecha++;
while (array[izquierda] >= pivote)
izquierda--;
}
return derecha;
}

// Intercambiar dos elementos en el array
private static void intercambiar(int i, int j, int[] array) {
int aux = array[i];
array[i] = array[j];
array[j] = aux;
}

public static int SeleccionRapida(int[] array, int k_menor, int i, int j) {
int indicePivote = buscaPivote(i, j, array);
if (indicePivote != -1) {
int pivote = array[indicePivote];
intercambiar(indicePivote, j, array); // pivote para la última posición
int pos = particion(i, j, pivote, array);
if (pos + 1 == k_menor) return pivote; // encontrado el elemento k_menor
else if (pos >= k_menor)
return SeleccionRapida(array, k_menor, i, pos - 1);
else return SeleccionRapida(array, k_menor, pos, j);
} else return indicePivote;
}