Problem paneli

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