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 ?
[Algorytmy] Suma elementów tablicy, parami niesąsiadującymi
-
- 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
Ostatnio zmieniony 28 wrz 2015, o 08:17 przez Afish, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- 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
Ponadto ze względów dydaktycznych można zaklepać poniższą metodę, która łatwo dostosowuje się do innych zadań:
Dodając spamiętywanie mamy dokładnie to, co poprzednio.
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);