Algorytm wyszukiwania najmniejszej ilości prostokątów.

Jeszcze trochę pokombinuję, bo wpadł mi do głowy pewien pomysł, ale jeśli nic z tego nie wyjdzie to zapewne to wykorzystam. 

1. Szukasz wszystkich możliwych rozmiarów prostokątów
2. Wybierasz ten, który ma największe pole.
3. Umieszczasz go na planszy w odpowiednim miejscu.
4. Wykonujesz kroki 1 - 3 aż do wypełnienia całej planszy.

Czy o takie coś Ci chodziło, czy chodzi o wszystkie możliwe rozwiązania? W podanym przez Ciebie przykładzie znalazłem inne rozwiązanie( dwa kwadraty, jeden o polu 4, a drugi o polu 1 ).

@jankowalski25 pewnie tak, ale jeśli chodzi o złożoność to trochę słabo :p
na pewno jest rozwiązanie w n^2

@ison: nie byłbym tego taki pewien :)

Ja bym szukał wszystkich możliwych kombinacji prostokątów na planszy umieścił gdzieś dane z liczbą prostokątów, a później wybrał rozwiązanie z najmniejszą liczbą prostokątów. To chyba jest do wykonania?

Ja natomiast wymyśliłem to tak, że szukamy prostokąta, który w jak najmniejszej części koliduje z pozostałymi prostokątami i ma przy tym jak największe pole(Jeśli kilka prostokątów koliduje z innymi w takiej samej części to dalsze czynności wykonujemy dla każdego z nich i wybieramy najlepsze rozwiązanie). Powtarzamy to do czasu zapełnienia całej figury. Wydaje mi się dość skuteczny, jeśli ktoś znalazł by lepsze rozwiązanie dla jakiejś figury niż daje ten sposób proszę o podanie go tutaj. Na razie nie mogę tego wykorzystać bo padły niektóre klawisze w laptopie, a na ekranowej bym to dwa tygodnie pisał. ;/