Algorytm wycinania kół przy jak najmniejszej stracie materiału

Dzień Dobry,

Ma ktoś pomysł, bądź zna algorytm służący do wycinania kółek na materiale NxN, tak aby wycinając kółka zużyć jak najmniej materiału.

Dokładnie :

Należy zaimplementowąć metode pack(), rozwiązującą zadania planowania podziału tafli w taki sposób by wybierając dowolne elementy znajdujace się w pliku wejściowym, dokonać takiego rozłożenia i upakowania ich na tafli by powierzchnia, która po pocięciu tafli pozostanie nie wykorzystana była możliwie najmniejsza.

Pozdrawiam,
Ezech

A jakas drobna podpowiedź, albo gdzie dalej szukać ratunku?

Na moich wykładach, panie studencie.

Jrj

@Ezechiel proponuje zacząć używać mózgu albo oczu. Wybór należy do ciebie. Po prawej stronie masz magiczne podpowiedzi które pokazują tematy podobne do twojego. I co jest pierwsze?
http://4programmers.net/Forum/Algorytmy/226952-pierogi_-_algorytm
Ale po co szukać, albo myśleć. Lepiej zakładać nowy temat...

Przy zalozeniu ze kola maja ta sama srednice to odpowiedz na Twoje pytanie to takze odpowiedz na pytanie: "ile najwiecej kol moge wcisnac?"
http://en.wikipedia.org/wiki/Circle_packing_in_a_square

wydaje mi sie, ze stosunkowo dobre przyblizenie dostaniesz robiac:

1. "na pale", czyli liczac dwa najbardziej opularne rozwiazanie (ukladasz warstwami, tylko dwa rozwiazania sa ciekawe i sprawdzasz gdzie Ci sie wiecej udalo)
2. Zrob to co wyzej, pozniej potraktuj kolka jako obiekty fizyczne w 2D, dodaj grawitacje zapusc symulacje, po chwili sie wszystko ustabilizuje, sprawdz czy mozesz dostawic jeszcze jakies kolko/kolka od gory.

O raby, zapomniaółem nadmienić że kółka są różnej długości.