Wypełnianie pokoju kartonami

0

Mam dość nietypowy problem...
Powiedzmy, że jest sobie jakieś pomieszczenie, np. pokój o powierzchni prostokąta, i chcę teraz wypełnić ten pokój kartonami o różnych wymiarach i chcę żeby program umiał jak najoptymalniej rozmieścić te kartony, żeby były jak najmniejsze luki pomiędzy nimi,
czyli wpisuję sobie:
10 kartonów o wymiarach 1,0 x 2,0 metry,
15 kartonów o wymiarach 0,5 x 3,0 metry itd.

a pokój ma wymiary np. 10,0 x 5,0 metrów
i żeby to było przedstawione np. graficznie w 2d
(oczywiście zamiast miary w metrach mogą być pixele)

przy czym:

  • nie można postawić jednego kartonu na drugi (zakładam, że kartony są wysokości pokoju),
  • nie można układać kartonów po skosie (tylko poziomo lub pionowo),
  • wymiary dodawanego kartonu będą takie, że zawsze zmieści się on, jeśli pokój będzie pusty.

Nie mam pojęcia jak się do tego zabrać. Nie wiem jak by miał wyglądać algorytm wybierający odpowiednie kartony i by musiał odrzucać te, które by już się nie mieściły w pokoju.

Z góry dziękuję za jakąkolwiek pomoc...

0

To mi przypomina coś w rodzaju klasycznego problemu plecakowego. Mi wpada tylko do głowy algorytm genetyczny, ale na pewno są prostsze sposoby na rozwiązanie czegoś takiego.

1 użytkowników online, w tym zalogowanych: 0, gości: 1