Подскажите идею реализации алгоритма бэктрекинга?
Подскажите пожалуйста идею бэктрекинга (поиска с возвратом) для решения такой задачи:
есть квадрат размером L. Есть неограниченное количество квадратиков размером от 1 до L-1. Нужно с помощью алгоритма найти минимальное число квадратов, из которых можно составить квадрат заданного размера L. Квадратики могут повторяться.
От чего оттолкнуться? Знаю что такое бэктрекинг, но не могу придумать как сделать перебор вариантов разбиения.
Ответы (1 шт):
Автор решения: default locale
→ Ссылка
На каждом шаге рекурсии у нас есть частично заполненный квадрат:
- Находим у него левую верхнюю свободную ячейку 1x1.
- Находим максимальный квадрат, который можно поставить в эту ячейку: со стороной S.
- Ставим в эту ячейку по очереди квадраты со стороной от S до 1 и переходим к следующему шагу.
Количество вариантов при полном переборе будет расти крайне быстро, но для малых квадратов подход должен сработать.