1

Подскажите пожалуйста идею бэктрекинга (поиска с возвратом) для решения такой задачи:

есть квадрат размером L. Есть неограниченное количество квадратиков размером от 1 до L-1. Нужно с помощью алгоритма найти минимальное число квадратов, из которых можно составить квадрат заданного размера L. Квадратики могут повторяться.

От чего оттолкнуться? Знаю что такое бэктрекинг, но не могу придумать как сделать перебор вариантов разбиения.

1

1 ответ 1

-1

На каждом шаге рекурсии у нас есть частично заполненный квадрат:

  • Находим у него левую верхнюю свободную ячейку 1x1.
  • Находим максимальный квадрат, который можно поставить в эту ячейку: со стороной S.
  • Ставим в эту ячейку по очереди квадраты со стороной от S до 1 и переходим к следующему шагу.

Количество вариантов при полном переборе будет расти крайне быстро, но для малых квадратов подход должен сработать.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.