Dany jest kształt pokoju i naszym zadaniem jest ułożenie paneli podłogowych w tym pokoju. Wszystkie panele są tego samego kształtu, dla uproszczenia zakładamy że są takie same z przodu i z tyłu, tak samo jak i z lewej i prawej strony. Pisząc prościej zakładamy, że posiadają środek symetrii. Dodatkowo, mówimy, że każdy panel możemy przeciąć ‘wszerz’, ale jego minimalna długość jest zadana. Dodatkowo, musimy zachować odpowiednią długość pomiędzy łączeniami.
Rozpatrzmy wersję problemu w której pokój ma rozmiar 5×40, panel ma rozmiar 1×10 o minimalnej długości 3 i minimalnej odległości między łączeniami 3:
Problem 1 | ||
Wersja 1 | ||
Pokój | Panel | |
Szerokość | 5 | 1 |
Długość | 40 | 10 |
Liczba zużytych paneli | 20 | |
MIN | 20 | |
MAX | 25 |
Dla tak postawionego problemu otrzymujemy rozwiązanie:
NR | 1 | 2 | 3 | 4 | 5 |
1 | 7 | 7 | |||
2 | 10 | 10 | 10 | 10 | 10 |
3 | 10 | 10 | 10 | 10 | 10 |
4 | 10 | 10 | 10 | 10 | 10 |
5 | 10 | 3 | 10 | 3 | 10 |
SUMA | 40 | 40 | 40 | 40 | 40 |
Rozwiązanie to jest optymalne – w tym sensie, że nie da się użyć mniej paneli niż zaproponowano. Dlatego, że pole pokoju to 200, a pole panelu to 10, czyli musimy zużyć minimum 200/10 = 20 paneli.
Rozważmy kolejny problem, gdy rozmiar pokoju wynosi 5×41:
Problem 2 | ||
Wersja 1 | ||
Pokój | Panel | |
Szerokość | 5 | 1 |
Długość | 41 | 10 |
Liczba zużytych paneli | 23 | |
MIN | 21 | |
MAX | 25 |
Proponowane rozwiązanie, analogiczne do poprzedniego – nie jest optymalne:
NR | 1 | 2 | 3 | 4 | 5 |
1 | 7 | 4 | 7 | 4 | 7 |
2 | 10 | 10 | 10 | 10 | 10 |
3 | 10 | 10 | 10 | 10 | 10 |
4 | 10 | 10 | 10 | 10 | 10 |
5 | 4 | 7 | 4 | 7 | 4 |
SUMA | 41 | 41 | 41 | 41 | 41 |
Sytuację możemy poprawić i otrzymujemy optymalne rozwiązanie:
NR | 1 | 2 | 3 | 4 | 5 |
1 | 7 | 3 | 6 | 3 | 7 |
2 | 10 | 10 | 10 | 10 | 10 |
3 | 10 | 10 | 10 | 10 | 10 |
4 | 10 | 10 | 10 | 10 | 10 |
5 | 4 | 8 | 5 | 8 | 4 |
SUMA | 41 | 41 | 41 | 41 | 41 |
Pójdźmy dalej, i rozważmy pokój o rozmiarach 5×42:
Problem 3 | ||
Wersja 3 | ||
Pokój | Panel | |
Szerokość | 5 | 1 |
Długość | 42 | 10 |
Liczba zużytych paneli | 22 | |
MIN | 21 | |
MAX | 25 |
Dla takiego przykładu najlepsze odnalezione rozwiązanie nie jest optymalne:
NR | 1 | 2 | 3 | 4 | 5 |
1 | 9 | 6 | 3 | 9 | 6 |
2 | 10 | 10 | 10 | 10 | 10 |
3 | 10 | 10 | 10 | 10 | 10 |
4 | 10 | 10 | 10 | 10 | 10 |
5 | 3 | 6 | 9 | 3 | 6 |
Kolejny problem dotyczy pokoju 5×43:
Problem 4 | ||
Wersja 1 | ||
Pokój | Panel | |
Szerokość | 5 | 1 |
Długość | 43 | 10 |
Liczba zużytych paneli | 22 | |
MIN | 22 | |
MAX | 25 |
Dla takiego problemu łatwo odnajdujemy optymalne rozwiązanie:
NR | 1 | 2 | 3 | 4 | 5 |
1 | 10 | 4 | 7 | 10 | 4 |
2 | 10 | 10 | 10 | 10 | 10 |
3 | 10 | 10 | 10 | 10 | 10 |
4 | 10 | 10 | 10 | 10 | 10 |
5 | 3 | 9 | 6 | 3 | 9 |
Dalej, rozważamy pokój 5×44:
Problem 5 | ||
Wersja 1 | ||
Pokój | Panel | |
Szerokość | 5 | 1 |
Długość | 44 | 10 |
Liczba zużytych paneli | 23 | |
MIN | 22 | |
MAX | 25 |
Tutaj nie znajdujemy optymalnego rozwiązania, ale przypuszczamy, że jest ono najlepsze:
NR | 1 | 2 | 3 | 4 | 5 |
1 | 10 | 6 | 10 | 6 | 10 |
2 | 10 | 10 | 10 | 10 | 10 |
3 | 10 | 10 | 10 | 10 | 10 |
4 | 10 | 10 | 10 | 10 | 10 |
5 | 4 | 8 | 4 | 8 | 4 |
Ostatni z przykładów jest relatywnie prosty – to pokój 5×45:
Problem 6 | ||
Wersja 1 | ||
Pokój | Panel | |
Szerokość | 5 | 1 |
Długość | 45 | 10 |
Liczba zużytych paneli | 23 | |
MIN | 23 | |
MAX | 25 |
Optymalne rozwiązanie:
NR | 1 | 2 | 3 | 4 | 5 |
1 | 10 | 5 | 10 | 5 | 10 |
2 | 10 | 10 | 10 | 10 | 10 |
3 | 10 | 10 | 10 | 10 | 10 |
4 | 10 | 10 | 10 | 10 | 10 |
5 | 5 | 10 | 5 | 10 | 5 |