elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Tutorial básico de Quickjs


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Java
| | | |-+  Algoritmo Voraz
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Algoritmo Voraz  (Leído 6,030 veces)
Compila

Desconectado Desconectado

Mensajes: 4


Ver Perfil
Algoritmo Voraz
« en: 5 Mayo 2022, 17:15 pm »

Hola, les escribo para saber si alguien me puede ayudar con un código que tengo que hacer en java.
El enunciado del problema consiste en: Necesitamos un solar/terreno con una superficie cuadrada de n metros cuadrados de lado. Para el solado podemos elegir diferentes baldosas cuadradas s0,s1,s2... metros de lado. Para reducir costes en la construcción pretendemos utilizar tan pocas baldosas como sea posible y por razones estéticas queremos usas baldosas enteras (aunque se mezclen los tamaños). El objetivo es implementar en java un código que resuelva el problema y que sea óptimo.

Adjunto el codigo que llevo realizado por ahora pero del cual no se cual es el problema por el que no puedo resolver el trabajo:

Código:
import java.util.Scanner;

/**
 * The Class BaldosasAV.
 * Clase que calcula mediante un algoritmo voraz la solución óptima para rellenar el suelo de un solar de dimensiones cuadradas
 * con baldosas también cuadradas de diferentes dimensiones.
 */

public class ProblemaBaldosas {
/**
* The main method.
*
* @param args the arguments
*/
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int baldosas[];
System.out.println("Introduzca las dimensiones del solar (metros cuadrados): ");
int solar = scan.nextInt();
System.out.println("Indique el número de baldosas diferentes: ");
int nBaldosas = scan.nextInt();
baldosas = new int[nBaldosas];

System.out.println("Inserte los tamaños de las baldosas: ");
for(int i = 0; i < nBaldosas; i++) {
System.out.println((i+1) + ".-Inserte un tamaño: ");
baldosas[i] = scan.nextInt();
}
algoritmoVoraz(baldosas, solar);
}

/**
* Algoritmo voraz.
*
* @param tamBaldosas the tam baldosas
* @param metros the metros
*/
private static void algoritmoVoraz (int[] tamBaldosas, int metros){

int solucion[][] = new int [metros] [metros];

int[] baldosas = mergesort(tamBaldosas, 0, tamBaldosas.length-1);

int actual, size;
int side = metros;
actual = baldosas.length-1;
size = baldosas[actual];
int []puestas= new int[baldosas.length];
for(int i = 0; i < side; i++) {
for(int j = 0; j < side; j++) {
while(solucion[i][j]==0 && actual >=0) {
size=baldosas[actual];
if(cabe(size, i, j, solucion, side)) {
for(int fila = i; fila < i + size; fila++) {
for(int col = j; col <j + size; col++) {
solucion[fila][col] = size;

}
}
puestas[actual]++;
}else {
actual--;
}
}
}
}

System.out.println();
for(int k=0; k<solucion.length; k++) {
for(int r=0; r<solucion.length; r++) {
System.out.print(solucion[k][r]);
}
System.out.println();
}
System.out.println("\nLas baldosas puestas son las siguientes: ");
for(int s=0; s<baldosas.length; s++) {
System.out.println("De tamaño "+baldosas[s]+" se han puesto "+puestas[s]+" baldosas.");
}

}

/**
* Método para saber si cabe una baldosa en el espacio restante.
*
* @param size the size
* @param r the r
* @param c the c
* @param solucion1 the solucion 1
* @param lado the lado
* @return true, si cabe la baldosa
*/
private static boolean cabe (int size, int r, int c, int [][] solucion1, int lado){
boolean fits = r + size <= lado && c + size <= lado;
if(fits){
  for(int row = r; fits && row < r + size; row++){
for(int col = c; fits && col < c + size; col++){
  if(solucion1[row][col] != 0) {
  fits = false;
  }
}
  }
}
return fits;
  }

/**
* Mergesort.
*
* @param array the array
* @param left posicion del numero de la izquierda
* @param right the right
* @return el array de enteros ordenado
*/
private static int[] mergesort(int[] array, int left, int right){
if (left < right) {
int mid = (left+right)/2;
mergesort (array, left, mid);
mergesort (array, mid + 1, right);
merge (array, left, mid, right);
}
return array;
}

/**
* Merge.
*
* @param a the a
* @param p the p
* @param q the q
* @param r the r
*/
private static void merge (int [ ] a, int p, int q, int r) {
int i = p, j = q+1, k = p;
int [ ] temp = new int [r-p+1];
for (int l = p; l <= r; l++) {
temp[l-p] = a[l];
}
while (i <= q && j <= r) {
if (temp[i-p] <= temp[j-p]) {
a[k] = temp[i-p]; i++;
} else {
a[k] = temp[j-p]; j++;
}
k++;
}
if (j-1 == r){
while (i <= q) {
a[k] = temp[i-p];
k++;
i++;
}
}
}

}



En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.348


Ver Perfil
Re: Algoritmo Voraz
« Respuesta #1 en: 6 Mayo 2022, 13:10 pm »

El problema se presta a resolverlo exactamente... es decir si se da una superficie exacta y las medidas de cada baldosa, puesto que admite que no se quieren 'romper' baldosas, debe tener solución exacta.

En el caso de no requerir exactitud, el problema se resuelve del siguiente modo:


Código:
baldosa(2) = x superficie
baldosa(1) = y superficie
baldosa(0) = z superficie
//donde baldosa(1) es menor que baldosa(2) y baldosa(0) menor que baldosa(1)

index = 2 // empezamos con la baldosa más grande
superficie = la que sea   // la superficie a cubrir
superficieOcupada = 0

Hacer mientras ((completo=FALSE) e (index >= 0))
    baldosa = baldosa(index)
    Mientras ((superficieOcupada + baldosa) < superficie)
        añadir 1 baldosa del tamaño index
        superficieOcupada += baldosa
    repetir

    Si ((superficieOcupada + baldosa) = superficie)
        añadir 1 baldosa del tamaño index
        completo= TRUE  //salir del bucle
    sino
        index -=1  //abordar con una baldosa más pequeña.
    fin
repetir

si (completo= FALSE)
   añadir 1 baldosa del tamaño 0  //sobrepasara la superficie total en este caso
fin si

 

Esta solución no es capaz de resolver con exactitud el problema, ya que puede darse el caso de que añadiendo la baldosa más pequeña, finalmente ocupe una superficie total mayor que la precisa para cubrir la deseada, pero es la mejor aproximación, la más óptima reduciendo el número de baldosas aunque existe la posibilidad de sobrepasar la superficie buscada, y por tanto cortar...

Al requerir una exactitud, debe considerarse un problema mucho más complejo, ya que cada baldosa tiene una superficie y si la superficie no se da en metros cuadrados, si no en largo x ancho, debe abordarse como dos bucles distintos, donde uno debe resolver el largo y otro resolver el ancho.
Y al solicitar una exactitud con baldosas enteras, exige una búsqueda con vuelta atrás, es decir que una baldosa grande añadida previamente sea retirada en favor de más de una pequeña.

Para dar un pseudocódigo, hace falta resolver la ambigüedad de si la superficie es teórica (dada en m²) o en ancho y largo...
de todos modos ahora mismo tengo que marcharme, pero si das respuesta, a la noche puedo mirarlo...


p.d.: Leyendo por encima tu código, observo que tanto la superficie como el tamaño de las baldosas se introducen por teclado y que además son cuadradas. Que sean cuadradas (y no rectangulares, o peor hexagonales, o culauiqer otro polígono) simplifica el caso...
...en cambio que se metan manualmente las medidas no garantiza que haya solución. Por ejemplo:
Si se introduce una superfice de 100cm x 100cm y 2 baldosas de 60x60 y 30x30, lo más aproximado será 90x90 y pasandose será 120x120.
El problema es similar a la devolución en monedas del cambio de una compra, solo que en el caso de las monedas (en su diseño), se ha previsto cubrir cualquier solución de cambio, pués suele haber monedas de 1 y multiplos de modo que es posible satisfacer siempre una solución exacta de devolución (salvo que se limite la cantidad de monedas existentes).

Un detalle que no ha sido precisado es si basta con conocer las baldosas que completan un área determinado, o si además se precisa saber la disposición de las baldosas sobre la superficie (esto último lo hac emás complejo). considera por ejemplo el juego del 'tangram', las piezas que lo componen rellenan la superficie que dan la spiezas, pero otro problema es emplazarlas para ocupar la superficie del puzzle', s decir la ubicación precisa de cada pieza respecto de la otra. No me parece haber leído en la descripción del problema si debe calcularse esto último o si basta con logras encontrar baldosas cuya suma de superficies equivalgan a la superfice que se desea rellenar. Nota que si cierto aspecto no se detalla en la descripción, no puede exigirse después como requisito (jamás a posteriori, para eso se da una especificación previa a la que hay que ceñirse).

Cuando te reportes (si te reportas y haces las preguntas precisas) se podrá avanzar en la solución, si todavía tienes lagunas...


« Última modificación: 7 Mayo 2022, 02:43 am por Serapis » En línea

Compila

Desconectado Desconectado

Mensajes: 4


Ver Perfil
Re: Algoritmo Voraz
« Respuesta #2 en: 5 Julio 2022, 07:58 am »

Buenas, continuando con el algoritmo uno de los apartados con respecto al código anterior me pide que lo modifique para devolver por consola la matriz con la primera baldosa que se coloque en ella definido con las siguientes variables :
Citar
int n =4;
int [] tilesSize ={1, 2, 5}
donde int n=4 es el tamaño de del suelo en metros cuadrados y tilesSize los tamaños de las baldosas. El codigo que he modificado comparado con el anterios es el siguiente:
Código:
public class ResultadoBaldosasModificado {

public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int baldosas[] = {1, 2 ,5};
int solar = 4;
int nBaldosas = 3;
}

algoritmoVoraz(baldosas, solar);

}

/**
* Algoritmo voraz.
*
* @param tamBaldosas the tam baldosas
* @param metros the metros
*/
private static void algoritmoVoraz (int[] tamBaldosas, int metros){

int solucion[][] = new int [metros] [metros];

int[] baldosas = mergesort(tamBaldosas, 0, tamBaldosas.length-1);

int actual, size;
int side = metros;
actual = baldosas.length-1;
size = baldosas[actual];
int []puestas= new int[baldosas.length];
for(int i = 0; i < side; i++) {
for(int j = 0; j < side; j++) {
while(solucion[i][j]==0 && actual >=0) {
size=baldosas[actual];
if(cabe(size, i, j, solucion, side)) {
for(int fila = i; fila < i + size; fila++) {
for(int col = j; col <j + size; col++) {
solucion[fila][col] = size;

}
}
puestas[actual]++;
}else {
actual--;
}
}
}
}

System.out.println();
for(int k=0; k<solucion.length; k++) {
for(int r=0; r<solucion.length; r++) {
System.out.print(solucion[k][r]);
}
System.out.println();
}
System.out.println("\nLas baldosas puestas son las siguientes: ");
for(int s=0; s<baldosas.length; s++) {
System.out.println("De tamaño "+baldosas[s]+" se han puesto "+puestas[s]+" baldosas.");

}

}

/**
* Método para saber si cabe una baldosa en el espacio restante.
*
* @param size the size
* @param r the r
* @param c the c
* @param solucion1 the solucion 1
* @param lado the lado
* @return true, si cabe la baldosa
*/
private static boolean cabe (int size, int r, int c, int [][] solucion1, int lado){
boolean fits = r + size <= lado && c + size <= lado;
if(fits){
  for(int row = r; fits && row < r + size; row++){
for(int col = c; fits && col < c + size; col++){
  if(solucion1[row][col] != 0) {
  fits = false;
  }
}
  }
}
return fits;
  }

/**
* Mergesort.
*
* @param array the array
* @param left posicion del numero de la izquierda
* @param right the right
* @return el array de enteros ordenado
*/
private static int[] mergesort(int[] array, int left, int right){
if (left < right) {
int mid = (left+right)/2;
mergesort (array, left, mid);
mergesort (array, mid + 1, right);
merge (array, left, mid, right);
}
return array;
}

/**
* Merge.
*/
private static void merge (int [ ] a, int p, int q, int r) {
int i = p, j = q+1, k = p;
int [ ] temp = new int [r-p+1];
for (int l = p; l <= r; l++) {
temp[l-p] = a[l];
}
while (i <= q && j <= r) {
if (temp[i-p] <= temp[j-p]) {
a[k] = temp[i-p]; i++;
} else {
a[k] = temp[j-p]; j++;
}
k++;
}
if (j-1 == r){
while (i <= q) {
a[k] = temp[i-p];
k++;
i++;
}
}
}

}


Lo que debe imprimir por consola es:
Citar
2 2 0 0
2 2 0 0
0 0 0 0
0 0 0 0
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines