Metody programowania / Ćwiczenia 6

Zadania z programowania dynamicznego.

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__

Zadanie 1 (Odcinki)

Dana jest tablica A zawierająca posortowane rosnąco liczby rzeczywiste oznaczające współrzędne punktów na prostej. Oblicz maksymalną sumę długości rozłącznych odcinków (tzn. nie stykających się nawet końcami), które można otrzymać łącząc wybrane sąsiednie punkty. Nie ma obowiązku użycia wszystkich punktów i nie wolno zmieniać zawartości tablicy.

Wskazówka

Przeglądaj A od lewej od prawej, pamiętając dwie liczby: najlepszą sumę używającą ostatniego punktu i najlepszą sumę nieużywającą ostatniego punktu.

Rozwiązanie

function Odcinki(N:integer; var A:array[1..N] of real) : real;
// N>=0; A posortowana
var i : integer;
   zost, bezost, zost_pom, bezost_pom : real;
begin
  zost:=0;
  bezost:=0;
  // zost i bezost oznaczaja maksymalna sumę dlugosci z i bez punktu i-1
  for i:=2 to N do begin
    bezost_pom:=max(zost,bezost);
    zost_pom:=bezost+A[i]-A[i-1]; 
      // dokladamy odcinek A[i-1]..A[i]
      // możemy bo odcinki odpowiadające sumie bezost nie blokują i-1 
    bezost:=bezost_pom;
    zost:=zost_pom;
  end;
  // zost i bezost oznaczaja maksymalna sumę dlugosci z i bez punktu N
  // wystarczy wybrać tą większą
  Odcinki:=max(zost,bezost);
end // Odcinki

Koszt czasowy: liniowy względem N.

Koszt pamięciowy: stały

Poprawność rozwiązania: poprawność rozwiązania opiera się na poprawności następujących rekurencyjnych wzorów:

bezost[1]=0
zost[1]=0
bezost[i]=max(zost[i-1],bezost[i-1])
zost[i]=bezost[i-1]+A[i]-A[i-1]

gdzie bezost[i] (odp. zost[i]) oznaczaja największą sumę odcinków od początku tablicy A aż do punktu A[i], nieblokujących (odp. blokujących) punkt A[i]. Istotnie jeśli chcemy mieć największą sumę odcinków nieblokujących i to można wziąć albo blokujące i-1 albo nieblokujące. Jeśli chcemy największą sumę odcinków blokujących i, to do największej sumy odcinków nieblokujących i-1 należy dodać długość odcinka z i-1 do i. Wartości początkowe są oczywiście poprawne (budząca wątpliwość wartość zost[1] nie jest istotna, bo w następnej operacji zost[1] występuje tylko w wyrażeniu max(zost[1],bezost[1]), więc jego wartość 0 niczego nie popsuje).

Ponieważ, jak widać ze wzorów do obliczenia wartości dla i wystarczy pamiętać wartości dla i-1, rezygnujemy z pamiętania całych tablic zost i bezost.

Rozwiązanie 2

function Odcinki2(N:integer; var A:array[1..N] of real) : real;
// N>=0; A posortowana
var i : integer;
   mozezost, bezost, mozezost_pom, bezost_pom : real;
begin
  mozezost:=0;
  bezost:=0;
  // mozezost i bezost oznaczaja maksymalna sumę dlugosci odcinków 
  // mogących i niemogących blokować punkt i-1
  for i:=2 to N do begin
    bezost_pom:=mozezost;
    mozezost_pom:=max(bezost+A[i]-A[i-1],mozezost);
      // albo bieżemy odcinki nieblokujące i-1 oraz odcinek A[i-1]..A[i]
      // albo odcinki potencjalnie blokujące i-1
    bezost:=bezost_pom;
    mozezost:=mozezost_pom;
  end;
  Odcinki2:=mozezost;
end // Odcinki2

Koszt czasowy: liniowy względem $N$.

Koszt pamięciowy: stały

Poprawność rozwiązania: poprawność rozwiązania opiera się na poprawności następujących rekurencyjnych wzorów:

bezost[1]=0
mozezost[1]=0
bezost[i]=mozezost[i-1]
mozezost[i]=max(bezost[i-1]+A[i]-A[i-1],mozezost[i-1])

gdzie bezost[i] (odp. mozezost[i]) oznaczaja największą sumę odcinków od początku tablicy A aż do punktu A[i], które nie mogą blokować (odp. mogą blokować) punkt A[i]. W tym rozwiązaniu pozbywamy się wątpliwości związanych z zost[1].

Ćwiczenie

Jak zmodyfikować nasz program, aby zamiast liczenia maksymalnej sumy, wypisywał ciąg odcinków o maksymalnej sumie?

Zadanie 2 (Kwadrat)

Dana jest tablica A typu array[1..N,1..M] of integer. Oblicz rozmiar (długość boku) największego kwadratu w tej tablicy składającego się z samych zer.

Wskazówka 1

W pomocniczej tablicy B tego samego typu trzymamy rozmiary największych kwadratów składających się z zer o prawym dolnym rogu w A[i,j]. Jeśli A[i,j]=0 to licząc B[i,j] patrzymy na B[i-1,j] i B[i,j-1] (oczywiście uważając na brzegi). W przypadku gdy B[i-1,j]=B[i, j-1]=r trzeba jeszcze zbadać A[i-r,j-r].

Rozwiązanie 1

function MaksKwadrat(N,M:integer; var A:array[1..N,1..M] of integer) : integer;
// N, M >=0; szukamy długości boku największego kwadratu w A składającego się z samych zer
var i,j,maks,r,bok : integer;
   B : array [1..N,1..M] of integer;
begin
  maks:=0;                          //na maks będziemy pamiętać bok największego dotychczas napotkanego kwadratu 
  for i:=1 to N do                  //wypełniamy pierwszy wiersz tablicy B
    if A[i,1]=0 then begin
      B[i,1]:=1
      maks:=1;
    end
    else B[i,1]:=0;
  for j:=1 to M do                  //wypełniamy pierwszą kolumnę tablicy B
    if A[1,j]=0 then begin
      B[1,j]:=1
      maks:=1;
    end
    else B[1,j]:=0;
  for j:=2 to M do
    for i:=2 to N do 
      if A[i,j]=0 then begin        //jeśli A[i,j]=0 to wartośc B[i,j] zależy od B[i-1,j] i B[i,j-1]
        r:=B[i,j-1];  
        if B[i-1,j]=r then          //jeśli B[i-1,j]=B[i,j-1] to trzeba zbadać A[i-r,j-r]
          if A[i-r,j-r]=0 then bok:=r+1
          else bok:=r
        else bok:=min(B[i-1,j], r)+1;
        B[i,j]:=bok;
        if bok > maks then maks:=bok;
      end
      else B[i,j]:=0;               //jeśli A[i,j] <> 0 wtedy B[i,j]=0
  MaksKwadrat:=maks;
end 

Koszt czasowy: liniowy względem N×M.

Koszt pamięciowy: liniowy względem N×M.

Wskazówka 2

Ponieważ nidgy nie sięgamy więcej niż o jeden wiersz w górę (i nigdy w prawo) wystarczy pomocnicza tablica B typu array [0..N] of integer (gdzie B[0]=0).

Rozwiązanie 2

function MaksKwadrat2(N,M:integer; var A:array[1..N,1..M] of integer) : integer;
// N, M >=0; szukamy długości boku największego kwadratu w A składającego się z samych zer
var i,j,maks,r,bok,stareB : integer;
   B : array [0..N] of integer;
begin
  maks:=0;                          //na maks będziemy pamiętać bok największego dotychczas napotkanego kwadratu 
  B[0]:=0;
  for i:=1 to N do                  //wypełniamy tablicę B zgodnie z pierwszym wierszem A
    if A[i,1]=0 then begin 
      B[i]:=1
      maks:=1;
    end
    else B[i]:=0;
  for j:=2 to M do                  //przechodzimy po kolejnych wierszach 
    for i:=1 to N do                //przechodzimy po kolejnych kolumnach
      if A[i,j]=0 then begin        //jeśli A[i,j]=0 to wartośc B[i] zależy od B[i-1] i B[i]
        r:=B[i];
        if B[i-1]=r then            //jeśli B[i-1]=r to trzeba zbadać A[i-r,j-r]
          if A[i-r,j-r]=0 then bok:=r+1
          else bok:=r
        else bok:=min(B[i-1], r)+1;
        B[i]:=bok;
        if bok > maks then maks:=bok;
      end
      else B[i]:=0;                 //jeśli A[i,j] <> 0 wtedy B[i]=0
  MaksKwadrat2:=maks;
end 

Koszt czasowy: liniowy względem N×M.

Koszt pamięciowy: liniowy względem N.

Zadanie 3 (Prostokąt)

Dana jest tablica A typu array[1..N,1..M] of integer. Oblicz maksymalne pole prostokąta składającego się z samych zer w tej tablicy.

Wskazówka 1

Ponieważ prostokątów zaczepionych prawym dolnym rogiem w danym polu może być dużo i nie bardzo wiadomo który z nich zapamiętać, rozwiązanie zadania z kwadratami nie przenosi sie bezpośrednio na zadanie o prostokątach.

Wskazówka 2

W pomocniczej tablicy B należy trzymać wysokość najdłuższego słupka zer w A o dolnym końcu w A[i,j]. W celu obliczenia maksymalnego pola prostokąta zaczepionego w A[i,j] należy przechodzić tablicę B indeksem r od prawej do lewej zaczynając od i, i obliczać maksymalne pola prostokątów o podstawie A[i-r,j] A[i,j].

Podobnie jak w zadaniu o kwadratach wystarczy do tego liniowa dodatkowa pamięć.

Rozwiązanie

function MaksProstokąt(N,M:integer; var A:array[1..N,1..M] of integer) : integer;
// N, M >=0; szukamy maksymalnego pola prostokąta w A składającego się z samych zer
var i,j,maks,r,podstawa,wysokośc,pole,  : integer;
   B : array [0..N] of integer;
begin
  maks:=0;                          //na maks będziemy pamiętać maksymalne pole dotychczas napotkanego prostokąta 
  B[0]:=0;
  for i:=1 to N do                  //wypełniamy tablicę B zgodnie z pierwszym wierszem A
    if A[i,1]=0 then begin
      B[i]:=1
      maks:=1;
    end
    else B[i]:=0;
  for j:=2 to M do 
    for i:=1 to N do begin
      if A[i,j]=0 then begin        //modyfikujemy B[i] 
        B[i]:=B[i]+1;
      else B[i]:=0;
      podstawa:=1;                  //w pętli obliczamy maksymalne pole prostokąta zaczepionego prawym dolnym 
      wysokość:=B[i];               //rogiem w A[i,j] 
      pole:=B[i];
      r:=i-1; ;       
      while B[r] <> 0 do begin      //nie przekroczymy zakresu tablicy B bo B[0]=0
        podstawa:=podstawa+1;
        wysokość:=min(wysokość, B[r]);
        pole:=max(pole, podstawa*wysokość);
      end;       
      if pole > maks then maks:=pole;
    end; //for i
  MaksProstokąt:=maks;
end 

Koszt czasowy: liniowy względem N×N×M.

Koszt pamięciowy: liniowy względem N.