Pomysł na stworzenie?

Question

Witam.

Jestem studentem II roku informatyki i z racji tego, że kończy się semestr dostałem projekt do napisania:
Dana jest tablica wymiaru n×2 wypełniona liczbami całkowitymi nieujemnymi. Należy wybrać z niej podzbiór o możliwie największej sumie, przy czym do zbioru nie mogą trafić liczby sąsiadujące ze sobą w pionie lub w poziomie. Wynikiem działania funkcji powinna być maksymalna suma takiego podzbioru, ewentualnie z wyliczeniem składników.

Nie do końca zrozumiałem o co w tym chodzi, więc poszedłem do prowadzącego przedmiot i nie chciał mi powiedzieć jak rozwiązać ten problem dla tablic n×2, ale podpowiedział jak to zrobić na jednej w dodatku to rozrysował. O to jak wygląda to rozrysowane:

A to jest kodm który udało mi się stworzyć:
http://pastebin.com/9d6r4DRd
 

1. Czy kod, który napisałem jest napisany dobrze?
2. Czy ma ktoś może jakiś pomysł jak to zrobić dla tablicy n×2 i czy mógłby ktoś to rozrysować albo w jakiś inny sposób wyjaśnić?

Pozdrawiam,
Rezorl.

Answer 1

To co pokazujesz to typowy problem rozwiązywany programowaniem dynamicznym.

Mamy przykładową tablicę:

1	1	4	...
4	2	2	...

Potrzebujemy sześć pomocniczych zmiennych a, b, c, olda, oldb, oldc

Na początek zajmijmy się pierwszą parą (1 i 4) - mamy trzy możliwości: a=0 nie weźmiemy żadnej liczby, b=1 weźmiemy jedynkę, c=4 weźmiemy czwórkę. Teraz przepisujemy a, b, c do zmiennych olda, oldb, oldc.

Teraz druga para (1 i 2) - znowu są trzy możliwości: nie weźmiemy żadnej liczby a=4 (bo do a trafia największa liczba spośród olda, oldb, oldc), druga możliwość - weźmiemy jedynkę czyli b=1+4 (bo do b trafia liczba z tablicy plus większa z liczb olda, oldc), trzecia możliwość - weźmiemy dwójkę czyli c=2+1 (bo do c trafia liczba z tablicy plus większa z liczb olda, oldb). Przepisujemy a, b, c do olda, oldb, oldc.

Dalej trzecia para (4 i 1) - analogicznie: a=5 (największa z olda, oldb, oldc), b=4+4 (większa z liczb olda i oldc), c=2+5 (większa z olda i oldb) Przepisujemy a, b, c do olda, oldb, oldc.

Tak jedziemy do końca. Największa liczba jaką uda się nam uzyskać jest szukaną sumą.

Zauważ tylko, że w podanym przykładzie zupełnie nie opłacało się brać liczby z drugiej pary.