Подскажите пожалуйста алгоритм решения такой задачки:

Дан прямоугольник с заданной длиной и шириной (например, 49 на 36). И есть 3 типа квадратов: например 3 на 3, 2 на 2 и 1 на 1. Нужно заполнить данный прямоугольник минимальным числом квадратов.

На данном этапе я делаю так: забиваю прямоугольник до упора большими квадратами, а затем в зависимости от того, сколько места осталось до границ, средними и малыми квадратами, но данное решение не кажется мне оптимальным.

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

Твоя задача это частный случай проблемы рюкзака (knapsack problem). Погугли на эту тему. 

А твой метод есть жадный алгоритм (быстро, просто, но не всегда оптимально)

Это сообщение отредактировал(а) AXS - 30.3.2010, 21:17