Wprowadzenie do zachłanności i dynamiki

18.10.2010 - Łukasz Zatorski
Trudność

Kiedy tablica będzie już gotowa, poruszamy się po niej wg następujących reguł:

  1. Na początku znajdujemy się w ostatnim wierszu, w stanie który nas interesuje.
  2. Powtarzamy, dopóki nie wykroczymy poza tablicę:
    • jeśli aktualne pole jest niepuste zaznaczamy je (innym kolorem) - przedmiot odpowiadający temu wierszowi jest elementem rozwiązania; przesuwamy się w lewo o liczbę pól odpowiadających jego wadze;
    • przesuwamy się jeden wiersz wyżej.

Poniższa animacja przedstawia przebieg naszego algorytmu dla danych z przykładu:

Tabela

Taką metodę, w której każdy podproblem liczymy tylko jeden raz nazywamy czasem programowaniem dynamicznym. Termin ten niekoniecznie musi mieć związek z komputerami – powstał on jeszcze przed popularyzacją języków programowania, i chodzi w nim bardziej o podejście – planowanie, niż o konkretną implementację. Nie mniej, rozwiązywanie tego problemu za każdym razem na kartce jest wysoce nieefektywną i żmudną pracą. Stąd programowanie dynamiczne bardzo często stosuje się w algorytmice. Zazwyczaj kod takiego rozwiązania nie wymaga żadnych zaawansowanych struktur danych – wystarczą przemyślane tablice (reprezentujące nasze pola) i pętle (które odpowiadają naszym czynnościom), co ilustruje poniższy pseudokod:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int MSIZE = 1000, PUSTO=-1;
int plecak[MSIZE], wynik = 0; /*kolejno: tablica do metody dynamicznej, wynik*/
int ilosc,pojemnosc,waga, wartosc; /*kolejno: ilosc przedmiotow, 
pojemnosc plecaka, waga i wartość przedmiotu*/
 
int main(){
  cin >> ilosc >> pojemnosc;
  for(int j=1;j<=pojemnosc;j++) plecak[j]=PUSTO;
  plecak[0]=0;
  for(int i=0;i<ilosc;i++){
    cin >> waga >> wartosc;
    for(int j=pojemnosc;j>=0;j--) 
      if(plecak[j]!=PUSTO){
        int nowa_waga = j + waga;
        int nowa_wartosc = plecak[j] + wartosc;
        if((nowa_waga<=pojemnosc) && (nowa_wartosc>plecak[nowa_waga])) 
          plecak[nowa_waga] = nowa_wartosc;
    }
  }
  for(int j=0;j<=pojemnosc;j++) if(plecak[j]>wynik) wynik = plecak[j];
  cout << wynik;
}

Bardzo ważne jest, by druga pętla przechodziła pola w porządku malejącym – w przeciwnym wypadku korzystając z jednej tablicy mogłoby się zdarzyć, że jakiś przedmiot policzymy więcej niż jeden raz!

Dla Ambitnych:

Jaki jest czas działania tego problemu? Dwie proste pętle nie sprawiają kłopotów z oszacowaniem złożoności przez $ O(n*m) $ gdzie $ n $ to ilość przedmiotów, a $ m $ rozmiar plecaka. Nie jest to jednak typowy algorytm wielomianowy – w ogólnym przypadku pojemność plecaka mogłaby bowiem zależeć wykładniczo od wielkości wejścia! W praktyce często nasze plecaki są niewielkie i dlatego podejście dynamiczne jest takie popularne i uznawane za wydajne. Zastanów się nad zmodyfikowaniem tej metody w taki sposób, by radziła sobie z dużymi wagami przy niewielkich ilościach przedmiotów (być może przyda się jakaś struktura danych inna niż tablica).

Pełne zrozumienie programowania dynamicznego wymaga wprawy – z czasem okazuje się ono doskonałym sposobem rozwiązywania innych problemów optymalizacyjnych.

4.846155
Twoja ocena: Brak Ocena: 4.8 (13 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com