Find the maximum total from top to bottom in triangle.txt (right click and ‘Save Link/Target As…’), a 15K text file containing a triangle with one-hundred rows.
NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 299 altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)
po zauważeniu, że lepiej liczyć opcje “od dołu piramidy”, zadanie przestaje być poważnym wyzwaniem. Rozwiązanie pokazane przez luckboy’a w problemie 18-stym tutaj również działa.
yyy… bardzo chętnie zobaczę algorytm liczący zadanie “od góry” - z zapamiętywaniem. Liczenie od dołu ma tą poważną zaletę, że niczego nie musisz zapamiętywać. Na bieżąco odrzucasz mniejszą sumę i kwalifikujesz większą do liczenia przy kolejnym wierszu.
gRuby, nie. W dużym skrócie nie. Największa liczba w dolnym rzędzie wcale nie musi być najlepszym punktem rozpoczęcia trasy (np. wyobraź sobie że sąsiadują z nią same jedynki w rzędzie wyżej). To jest właśnie clou całej złożoności problemu.
Ciekawe, prosimy o wyjaśnienie “krok po kroku” dla dummies. Wiem, że algorytm od dołu działa dobrze ale za cholerę nie mogę go zrozumieć (obwiniam poniedziałkowy poranek )
jeśli czegoś nie rozumiem, proszę o wyjaśnienie;
mój sposób rozumowania:
zaczynamy od najniższego wiersza i wiersza powyżej,
dla każdego utworzonego “trójkąta” (liczba z wiersza wyższego + dwie liczby z wiersza poniżej) robimy dwie sumy i do dalszych obliczeń używamy tej większej.
jeśli ten tok rozumowania jest słaby to wykazałem się niesamowitym szczęściem licząc oba zadania (18, 67) prawidłowo w prostym skrypcie w minimalnym (jak można się domyślić) czasie …
(t.length-2).downto(0) { |i| 0.upto(t[i].length-1) { |j| t[i][j] += t[i+1][j…j+1].max } }
p t[0][0][/code]
Rozwiązanie wydaje mi się poprawne dla każdego trójkąta Tomash, chociaż wciąż go nie rozumiem, umysł zniszczony pisaniem CMS’ów w Railsach poddaje się przy algorytmice - to straszne uczucie
rows = []
File.open("triangle.txt").each do |t|
rows << t.split(' ')
end
down_row = rows[rows.size-1]
(rows.size-1).downto(1) do |p|
new_row = []
upper_row = rows[p-1]
0.upto(upper_row.size-1) do |s|
left_sum = down_row[s].to_i + upper_row[s].to_i
right_sum = down_row[s+1].to_i + upper_row[s].to_i
if left_sum > right_sum
new_row << left_sum
else
new_row << right_sum
end
end
down_row.replace new_row
puts "oto nowe watrości #{down_row}"
end
dla jasności po każdej pętli pokazuję każdorazowo tablicę z nowymi wartościami maksymalnymi. Ostatnia wartość jest rozwiązaniem.
[quote=Tomash]gRuby, nie. W dużym skrócie nie…
Miałeś szczęśliwe dane wejściowe, to wszystko.[/quote]
Czy mogę Ciebie prosić Tomash o wskazanie błędu w rozumowaniu, ewentualnie o podanie mniej szczęśliwych danych ?
Algorytm jest bardzo prosty :). Podstawowe założenie jest takie, że do każdego miejsca w trójkącie można tak naprawdę dojść albo z lewego górnego sąsiada albo z prawego (no może poza drugim wierszem). No i teraz największa suma dla danego miejsca to suma dojścia do lewego albo prawego sąsiada plus wartość w danym miejscu.
Algorytm dla każdego wiersza leci po wszystkich pozycjach i dla każdej wybiera większą sumę z jego sąsiadów, dodaje swoją wartość i zapisuje największą sumę dla danego wiersza. Chyba trochę zakombinowałem
Dla tych danych co podał drogus te sumy wyglądały by tak:
)