Mejor manera de llenar un tablero de $8\times 8$

Question

Usted tiene un $8\times 8$ Acorazados de la junta y de la necesidad de los acorazados de tamaños $1\times 1$, $1\times 2$, $1\times 3$, $1\times 4$, $1\times 5$ en la junta para cubrir tanto de la junta como sea posible. El barco no puede tocar a otro de la nave, incluso en las esquinas.

Usted puede colocar tantos de cualquier tamaño que desee, ¿cuál es el número máximo de plazas que pueden llenar? Creo que la respuesta es de 30, aunque no está seguro de cómo demostrar que es el más alto.

También cómo se podría ir sobre la resolución de este para un $n\times n$ junta. Esto probablemente se refiere a cómo probar la respuesta de la primera parte.

Answer 1

EDITAR:

Parece como si usted puede conseguir 32:

Answer 2

32 es el mejor que usted puede conseguir. Usted puede substituir cada $k\times 1$ nave por un $(k+1)\times 2$ rectángulo en un $9\times 9$ junta, y los barcos son legalmente posicionado iff los rectángulos no se superponen. Si $n$ barcos recorren $m$ plazas, a continuación, los rectángulos de la cubierta $2(m+n)$ plazas, por lo $m+n\le 40$. Por lo tanto, si hay al menos 8 de los buques, que no puede cubrir más de 32 plazas. OTOH, 6 barcos de la cubierta en la mayoría de las 30 plazas. Si son 7 los buques y en la mayoría de las 4 de ellos son de tamaño 5, se cubren en la mayoría de los 32 plazas. Así, considere la posibilidad de 5 buques de tamaño 5 se coloca en el tablero. Al menos 3 de ellas son paralelas entre sí. Podemos suponer que son horizontales. Cada uno de ellos está más cerca de un borde vertical de la junta que el otro. Podemos suponer que dos de ellos están más cerca del borde izquierdo. Entonces no puede haber una vertical de 5-plaza de barco en cualquiera de las 6 columnas de la izquierda, por lo que hay 4 horizontal de los buques y 1 vertical. Pero entonces no hay espacio para otra nave única.

No he revisado cuidadosamente los detalles, me dejó, pero tengo la esperanza de que el de arriba es esencialmente correcta de croquis.

Answer 3

Considere el grafo con vértices correspondientes a la colocación de un único buque de guerra, y una arista entre los vértices si el correspondiente colocaciones son incompatibles (superpuestas o tocar). Su problema es un Máximo Ponderado Conjunto Independiente problema en este gráfico. Esta es una bien estudiada pero el problema difícil para el que existen varios algoritmos. En general es NP-completo. No sé si este particular conjunto de instancias es NP-completo, pero eso no inspira la confianza que el $n \times n$ problema tiene una fácil solución.