Подсчитать максимальное количество прямоугольников, которые могут быть размещены внутри символа

Question

Мне нужно решение довольно сложной проблемы. Точно, мне нужно вычислить количество прямоугольников, которые можно поместить внутри буквы / символа с заданным размером, учитывая, что все прямоугольники имеют одинаковый размер, но это (размер) и сама буква / символ (некоторого обычного определенного шрифта) сами может быть изменен пользователем (это будет использоваться в качестве веб-калькулятора цены вывески). Если описать это графически, это выглядит так:

альтернативный текст http://habreffect.ru/files/319/aab0644b9/img.png

Любые идеи или полезные ссылки будут высоко ценится. Заранее спасибо

Answer 1

О размере символов:

Печать символа в растровом изображении и подсчет черных регионов

Answer 2

2D-упаковка Эта страница может немного прояснить ситуацию: http://users.cs.cf.ac.uk/C.L.Mumford/heidi/Background.html

На вики-странице по упаковке в бен: en.wikipedia.org/wiki/Bin_packing_problem есть ссылка на пакет программного обеспечения, который может пригодиться: http://code.google.com/p/caparf/

Вам не повезло, что это NP-Hard. Вам повезло, что эта тема широко исследована и имеет множество алгоритмов аппроксимации. В самой современной литературе по упаковке в мусорное ведро должна быть информация, которая должна помочь.