|
dziel i zwyciezaj
Np. sortowanie przez scalanie - poszukaj w sieci jest tego mnostwo. Koszt obliczeniowy nlogn
Programowanie zachlanne.
Zalozmy ze masz plecak o pakownosci podanej w kg, jestes w banku i musisz wyniesc jak najwiecej. Masz rozne sztabki kazda sztabka ma swoja wage i cene. obliczasz wspolczynnik cena/waga dla kazdej sztabki i pakujesz do worka te o najwyzszych wspolczynnikach az nie bedziesz mogl wiecej. W ten sposob nie otrzymasz optymalnego pakowania, tylko wlasnie takie zachlanne.
Przeszukanie z nawrotami - nie wiem.
Programowanie dymaniczne.
Przeciwienstwo programowania zachlannego. Wezmy problem jak poprzednio. Zalozmy ze masz plecak o danej pakownosci N. Tworzysz tablice od 1 do N w ktorej wpisujesz numery ostatniej zapakowanej sztabki ktora zostala dolozona by otrzmac obciazenie z indeksu. Potem idziesz droga od ostaniego indexu i masz optymalne upakowanie.
|