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++;
}
}
}
}
/**
* 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++;
}
}
}
}