[Algorytmy] Suma elementów tablicy, parami niesąsiadującymi

matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

[Algorytmy] Suma elementów tablicy, parami niesąsiadującymi

Post autor: matinf »

Chcemy znaleźć największą możliwą sumę elementów tablicy taką, że nie bierzemy sąsiadujących elementów. Szukamy efektywnego algorytmu.

Pokazałem taki dynamik, który wydaje się, że działa.

\(\displaystyle{ v}\) - element \(\displaystyle{ a}\) wchodzi do sumy.
\(\displaystyle{ t}\) - element \(\displaystyle{ a}\) nie wchodzi do sumy.
\(\displaystyle{ v[0]=t[0] = 0\\
v = a + t[i-1]\\
t = \max (v[i-1], t[i-1])
}\)

Chcę więc dowieść poprawności, ale nie wiem czy taki dowód indukcyjny tutaj jest poprawny (bo w sumie tak na prawdę mówię co się dzieje).
Powiedzmy, że chcemy wykonać krok dla \(\displaystyle{ i+1}\) (dla \(\displaystyle{ 1..i}\) jest poprawnie z zał. ind.) No więc są dwie możliwości:
1. Biorę \(\displaystyle{ a[i+1]}\). Wówczas \(\displaystyle{ v[i+1] = a[i+1] + t}\).
2. Nie biorę \(\displaystyle{ a[i+1]}\). Wówczas \(\displaystyle{ t[i+1] = \max (t, v)}\);
wynikiem jest \(\displaystyle{ \max (t[i+1], v[i+1])}\).

Co o tym sądzicie ?
Ostatnio zmieniony 28 wrz 2015, o 08:17 przez Afish, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Algorytmy] Suma elementów tablicy, parami niesąsiadującymi

Post autor: Afish »

Wydaje się poprawne.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

[Algorytmy] Suma elementów tablicy, parami niesąsiadującymi

Post autor: matinf »

Dzięki wielkie.
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Algorytmy] Suma elementów tablicy, parami niesąsiadującymi

Post autor: Afish »

Ponadto ze względów dydaktycznych można zaklepać poniższą metodę, która łatwo dostosowuje się do innych zadań:

Kod: Zaznacz cały

int array[];
int length;

int getSum(int elementIndex){
    if(elementIndex < 0) return 0;
    if(elementIndex >= length) return 0;
    int sumIfWeTakeCurrentElement = array[elementIndex] + getSum(elementIndex - 2);
    int sumIfWeDontTakeCurrentElement = getSum(elementIndex - 1);
    return max(sumIfWeTakeCurrentElement, sumIfWeDontTakeCurrentElement);
}

int result = getSum(length - 1);
Dodając spamiętywanie mamy dokładnie to, co poprzednio.
ODPOWIEDZ