Cześć, chciałbym rozwiązać następujący problem:
mamy prostokątną planszę o wysokości h i szerokości w, składa się z w*h pól, na niektórych polach są monety, startujemy z lewego górnego rogu i kończymy na prawym dolnym. Można poruszać się tylko w prawo i na dół. Algorytm ma wyznaczyć maksymalną liczbę monet, które można zebrać po drodze na podstawie podanej planszy.
Podobno należy użyć programowania dynamicznego, ale jestem nowicjuszem i od dłuższego czasu już nie mogę na nic wpaść - co prawda znalazłem jakieś algorytmy zachłanne, ale nie są poprawne, bo istnieją odpowiednie kontrprzykłady.
Czy mógłbym prosić o jakieś wskazówki pomocne w pokonaniu tego zadania? Z góry dziękuję.
[Algorytmy] Zbieranie monet po drodze
-
- 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] Zbieranie monet po drodze
W każdym polu możesz zdobyć liczbę monet będącą maksimum z pola powyżej oraz z pola z lewej strony, plus ewentualna moneta na tym polu. Iterujesz po planszy od górnego lewego rogu do dolnego prawego po wierszach i aktualizujesz wartości. Potrzebujesz pamiętać tylko dwa wiersze (aktualnie analizowany i jeden wyżej).
-
- Użytkownik
- Posty: 1130
- Rejestracja: 1 lis 2008, o 22:33
- Płeć: Mężczyzna
- Podziękował: 72 razy
- Pomógł: 156 razy
[Algorytmy] Zbieranie monet po drodze
Idziesz od drugiej strony planszy (czyli od prawego dolnego rogu) i dla każdego pola sprawdzasz wartość monet na dół i na prawo od niego. Bierzesz większą z nich i dodajesz do wartości badanego pola. Liczba którą będziesz miał w lewym górnym rogu będzie twoim rozwiązaniem.
-
- Użytkownik
- Posty: 41
- Rejestracja: 4 cze 2013, o 15:28
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 8 razy
[Algorytmy] Zbieranie monet po drodze
Rzeczywiście, że też na to nie wpadłem. Już myślałem o jakimś iterowaniu po diagonalach, a to jednak wcale nie ma przerażającego rozwiązania. Implementacja w C++ zakończona, wszystko działa, wybrałem sposób Afish'a, bo na dobrą sprawę czy idzie się od końca, czy od początku, to jest to bez różnicy, bo można planszę obrócić i ma się zamienione rogi. Bardzo dziękuję za pomoc i przy następnym problemie nie będę się wahał gdzie napisać.