Algorytm zachłanny

Algorytm zachłanny wyznacza rozwiązanie w każdym kroku dokonując zachłannego tj. najlepiej rokującego w danym momencie wyboru rozwiązania częściowego przy tym nie zachowując sensu działań poprzednich,  dokonując decyzji lokalnie optymalnej, wyboru najlepszego.

Firma produkuje klocki w trzech rozmiarach dostępnych w opakowaniach A, B, C. W każdym opakowaniu znajdują się dwa klocki w kształcie kwadratu 1x1, kxk (A: k=2, B: k=3, C: k=4) i jeden prostokąt kx1. Firma otrzymała zamówienie na produkcję klocków tak, żeby można było z nich ułożyć kwadraty o wymiarach do 13x13. Obliczyć z ilu klocków będzie się składał kwadrat A13, B13, C13 tzn. ile klocków należy włożyć do opakowania A, B, C i jakie?

Wyznaczamy kolejne ilości klocków znajdujących się w opakowaniach A, B, C z których można zbudować kwadraty:
A:

A_1(1x1)=1 _(1x1) = 1                                               

A_2(2x2)=1 _(2x2) = 1                                              
A_3(3x3)=1 _(2x2) + 2 _(2x1) +1 _(1x1) = 4                         
A_4(4x4)=4 _(2x2)= 4

A_5(5x5)=4 _(2x2) + 4 _(2x1) + 4 _(1x1) = 9           

A_6(6x6)=9 _(2x2)= 9

A_7(7x7)=9 _(2x2) + 6 _(2x1) + 1 _(1x1) = 16

A_8(8x8)=16 _(2x2) 
A_9(9x9)=16 _(2x2) + 8 _(2x1) + 1 _(1x1) = 25  
A_10(10x10)=25 _(2x2)
A_11(11x11)=25 _(2x2) + 10 _(2x1) + 1 _(1x1) = 36
A_12(12x12)=36 _(2x2)
A_13(13x13)=36 _(2x2) + 12 _(2x1) + 1 _(1x1) = 49
A_14(14x14)=49 _(2x2)
A_15(15x15)=49 _(2x2) + 14 _(2x1) + 1 _(1x1) = 64
A_16(16x16)=64 _(2x2)
A_17(17x17)=64 _(2x2) + 16 _(2x1) + 1 _(1x1) = 81
A_18(18x18)=81 _(2x2)
A_19(19x19)=81 _(2x2) + 18 _(2x1) + 1 _(1x1) = 100
A_20(20x20)=100 _(2x2)

B:

B_1(1x1)=1 _(1x1) = 1                                               

B_2(2x2)=4 _(1x1) = 4                                              
B_3(3x3)=1 _(3x3)                        
B_4(4x4)=1 _{(3x3) + 2 (3x1) + 1 (1x1)}= 4

B_5(5x5)=1 _(3x3) + 4 _(3x1) + 4 _(1x1) = 9           

B_6(6x6)=4 _(3x3)= 4

B_7(7x7)=4 _(3x3) + 4 _(3x1) + 1 _(1x1) = 9  
B_8(8x8)=4 _(3x3) + 8 _(3x1) + 4 _(1x1) = 16
B_9(9x9)=16 _(3x3) = 9  
B_10(10x10)=9 _(3x3) + 6 _(3x1) + 1 _(1x1) = 16
B_11(11x11)=9 _(3x3) + 12 _(3x1) + 4 _(1x1) = 25
B_12(12x12)=16 _(3x3)
B_13(13x13)=16 _(3x3) + 8 _(3x1) + 1 _(1x1) = 25
B_14(14x14)=16 _(3x3) + 16 _(3x1) + 4 _(1x1) = 36
B_15(15x15)=25 _(3x3)
B_16(16x16)=25 _(3x3) + 10 _(3x1) + 1 _(1x1) = 36
B_17(17x17)=25 _(3x3) + 20 _(3x1) + 4 _(1x1) = 49
B_18(18x18)=36 _(3x3)
B_19(19x19)=36 _(3x3) + 12 _(3x1) + 1 _(1x1) = 49
B_20(20x20)=36 _(3x3) + 24 _(3x1) + 4 _(1x1) = 64

C:

C_1(1x1)=1 _(1x1) = 1                                               

C_2(2x2)=4 _(1x1) = 4                                              
C_3(3x3)=9 _(1x1) = 9                         
C_4(4x4)=1 _(4x4) =  1

C_5(5x5)=1 _(4x4) + 2 _(4x1) + 1 _(1x1) = 4           

C_6(6x6)=1 _(4x4) + 4 _(3x1) + 4 _(1x1) = 9

C_7(7x7)=1 _(4x4) + 6 _(3x1) + 9 _(1x1) = 16    
C_8(8x8)=4 _(4x4) = 4
C_9(9x9)=4 _(4x4) + 4 _(3x1) + 1 _(1x1) = 9   
C_10(10x10)=4 _(4x4) + 8 _(3x1) + 4 _(1x1) = 16
C_11(11x11)=4 _(4x4) + 12 _(3x1) + 9 _(1x1) = 25
C_12(12x12)=9 _(4x4)
C_13(13x13)=9 _(4x4) + 6 _(3x1) + 1 _(1x1) = 16
C_14(14x14)=9 _(4x4) + 12 _(3x1) + 4 _(1x1) = 25
C_15(15x15)=9 _(4x4) + 18 _(3x1) + 9 _(1x1) = 36
C_16(16x16)=16 _(4x4)
C_17(17x17)=16 _(4x4) + 8 _(3x1) + 1 _(1x1) = 25
C_18(18x18)=16 _(4x4) + 16 _(3x1) + 4 _(1x1) = 36
C_19(19x19)=16 _(4x4) + 24 _(3x1) + 9 _(1x1) = 49
C_20(20x20)=25 _(4x4)

Co najważniejsze, algorytm ten jest na tyle zachłanny, że w wynikach ilości klocków z których można ułożyć kwadraty bazuje na liczbach kwadratowych 1, 4, 9, 25, 36, 49, ...

 n |  A |  B |  C |

 1 |  1 |  1 |  1 |

 2 |  1 |  4 |  4 |

 3 |  4 |  1 |  9 |

 4 |  4 |  4 |  1 |

 5 |  9 |  9 |  4 |

 6 |  9 |  4 |  9 |

 7 | 16 |  9 | 16 |

 8 | 16 | 16 |  4 |

 9 | 25 |  9 |  9 |

10 | 25 | 16 | 16 |

11 | 36 | 25 | 25 |

12 | 36 | 16 |  9 |

13 | 49 | 25 | 16 |
14 | 49 | 36 | 25 |

15 | 64 | 25 | 36 |
16 | 64 | 36 | 16 |
17 | 81 | 49 | 25 |
18 | 81 | 36 | 36 |
19 | 100 | 49 | 49 |
20 | 100 | 64 | 25 |

              ...

Post nr 130