Задача о стене

[Poma][a]

Ну задан набор блоков, а причем тут "минимальный размер стены"?

Посути минимальный размер стены равен 1. Но этот вариант нам не интересен. Лучше рассмотреть стенку, в постройке которой можно применить любой из возможных блоков.
А минимальная такая стена - размером 8 на 8

[rrrFer]

Посути минимальный размер стены равен 1. Но этот вариант нам не интересен. Лучше рассмотреть стенку, в постройке которой можно применить любой блок.
А минимальная такая стена - размером 8 на 8

Вы ребят странные оба. Почему "такой вариант не интересен"? - ваш алгоритм не будет работать на стенах, где нельзя применить блок 8х8? Почему вы додумали условие?

"задан набор блоков" означает, чтото-типа

Блоков 1х1 - 1шт
блоков 2х1 - 3 шт
...
блоков 8х8 - 0шт

Т.е. таких блоков вполне может и не быть (противное в условии не сказано).

Мало того, если даже такой блок есть - он не обязательно должен использоваться, в оригинальной задаче специально написано:

(не обязательно использовать все блоки)

Лучше рассмотреть стенку, в постройке которой можно применить любой блок.

Лучше решать поставленную задачу, а не придумывать новую.

[Poma][a]

Да потому что ответ там очевиден

ваш алгоритм не будет работать на стенах, где нельзя применить блок 8х8?

Дак может будем решать задачу с теми же условиями, но снизив планку? Возьмем те же блоки, но уменьшим размер стены

[Аватар]

У-у, задача о покрытии множества. Для этого целые теории разрабатывают. Я бы погуглил на предмет того выделенного жирным

[rrrFer]

У-у, задача о покрытии множества.

Я не мог вспомнить как оно называется, спасибо. Но тут совсем другая задача:
1) не требуется искать оптимальное решение (в классических постановках требуется что-то максимизировать или минимизировать).
1.1) В этой задаче не может использоваться часть блока, а в классической задаче - может (потому что покрытие может быть больше исходного множества)
1.2) Опять же тут не могут остаться непокрытые кирпичи в стене, а в покрытии множества - могут (т.к. задача стоит "минимизировать, а не покрыть все"
2) тут заданы константы, которые резко меняют задачу. И вроде бы она перестает быть NP-полной.

[Utkin]

Дак все кирпичи одного размера.

А блоки нет . Разбитие стены на независимые прямоугольные участки по мне годное решение.

[8Observer8]

Кстати, с помощью решения этой задачи можно написать бота тетриса, который знает все блоки и может выдавать какой захочет. Задача такого бота была бы определить: возможно ли, имея данные блоки, сыграть в ноль (и сколько таких способов укладки)

[Smitt&Wesson]

У меня - лучше.

[Utkin]

У меня - лучше.

Дык, кто спорит?

[Аватар]

Сообщение от Utkin

Дык, кто спорит?

Дык Смитт и спорит, сам с собой