Odwrócony trójkąt – znalezienie drogi o najmniejszej liczbie punktów

Mam za zadanie odczytać plik txt, w którym utworzony jest odwrócony trójkąt zbudowany z liczb, wygląda to mniej więcej tak:

A następnie zaczynając od góry znaleźć drogę taką by zebrać jak najmniej punktów docierając na sam dół. Tzn. np. gdy zacznę od 60 to następnie mogę się udać tylko na pola poniżej, czyli 45 albo 65 itd.
Odczyt z pliku i wyświetlenie trójkąta zrobiłem, natomiast nie potrafie poradzić sobie z tą drogą, myślałem nad algorytmami djikstry, kruskala czy prima bo te mniej więcej znam, ale nic z tego ;/.
Wydaje mi się, że bez dużej ilości pętli będzie ciężko ;/. Jeśli macie jakieś pomysły, rady jak to zrobić to za każdy będe bardzo wdzięczny ;)

Te liczby mogą być ujemne?

pingwindyktator napisał(a):

Te liczby mogą być ujemne?

Chyba bez znaczenia, skoro nie może być i tak cykli...

Jakoś rekurencyjnie może spróbować?

A nie podchodzi to pod dynamic?

@koszalek-opalek: chyba właśnie ma to znaczenie. Sądze, że jedynym rozwiązaniem byłoby potraktowanie tego jako graf (znamy krawędzie) i sprawdzenie wszystkich możliwości. Jeśli liczby nie mogą być ujemne, to możemy to lekko optymalizować, ucinając niektóre ścieżki. Przykład: mamy znalezioną dotychczas najlepszą ścieżke o wyniku 50. Jesteśmy w trakcie szukania kolejnej ścieżki, dotychczasowy wynik to 45 i mamy jeszcze 10 "poziomów" drzewa w dół do przejścia. Jeśli liczby są >= 1, to wiemy, że nasz wynik będzie >= 45 + 10 i możemy "odciąć" tę ścieżke.

07    95    60    33    19    21
   19    45    65    18    07
      16    74    21    22
         88    11    76
            23    44
               01

@MichalMP11: masz jakieś testy do tego?

Nie ma znaczenia jak nie ma cykli -- a tu możesz iśc tylko w dół.

Dowód, że ujemne nie mają znaczenia:

• wybieramy największą co do wartości bezwzględnej liczbę X;
• dodajemy (|X|+1) do każdej liczby w trójkącie;
• i oczywiście nie zmienia to ścieżki, tylko powiększa jej sumę o (|X|+1)*(liczba poziomów).
  :)

Chyba nie do końca sie rozumiemy (albo to ja gadam głupoty). Rozważmy takie drzewo:

1    1    2    3
   1    9    3
      1    1
         1

Po którymś kroku algorytmu mamy znalezione dotychczasowe najlepsze rozwiązanie - niech będzie to "lewa" strona drzewa, 1-1-1-1. Szukamy innego, lepszego rozwiązania. W którymś z kolejnych kroków rozpatrujemy rozwiązanie 1-9 ("prawie lewa" strona drzewa). Jeśli liczby nie mogą być ujemne, to już na tym etapie możemy powiedzieć, że każde rozwiązanie 1-9-* będzie gorsze od naszego najlepszego 1-1-1-1 i nie musimy iść niżej w drzewie (chyba, że liczby mogą być ujemne i po drodze znajdziemy -10000 :) )

No dobrze, ale do Twojego rozumowania zastosuj mój szkic dowodu... I okazuje się, że nie ma to znaczenia... To znaczy takie dezycje o lepszości możemy zawsze podjąć, jeśli wiemy, że pozostałe liczby są w jakimś przedziale -- ale nie ma to związku z ujemnością liczb, tylko z tym, co wiemy do tej pory...

Okej, mój algorytm, nietestowany, więc może nie do końca działać. :)

Rekurencyjny. :)

Zakładamy, że dany jest trójkąt w postaci tablicy t indeksowanej t[wiersz][kolumna], gdzie wiersz jest od 0 do N-1, a kolumna jest od 0 do N-1-wiersz.

def najkrotsza_droga(N, t, pocz_wiersz, pocz_kol, dotychczasowy_wynik=0):
    dotychczasowy_wynik += t[pocz_wiersz][kon_wiersz]
    if pocz_wiersz == N-1:
        return dotychczasowy_wynik
    return min(najkrotsza_droga(N, t, pocz_wiersz+1, pocz_kol-1, dotychczasowy_wynik), 
               najkrotsza_droga(N, t, pocz_wiersz+1, pocz_kol, dotychczasowy_wynik))

Brakuje sprawdzania, czy nie wyłazimy poza trójkąt na boki (przed ostatnim returnem), ale to pozostawiam jako zadanie dla czytelnika... :)

EDIT: drobne poprawki :)

Okej, powinienem spytać bardziej generalnie - czy wiemy w jakim przedziale są liczby. Ja założyłem, że albo są naturalne, albo są całkowite - stąd moje pytanie.

Więc tak:

• wstawiłem screena trójkąta bo poprzedni mi się "rozjechał", niestety wczoraj tego nie zauważyłem
• w tym przypadku liczby są tylko >=1 i mniejsze niż 100
• dzisiaj wieczorem przetestuje wasze pomysły bo wracam do domu około 20, wszystkim dziękuje

Widzę kolega również rozwiązuje Project Euler (https://projecteuler.net/problem=18) ;-)
Rzuć okiem np. na takie rozwiązanie - jeśli nie musisz znać ścieżki.

Edit: ach, tu jest nieco inaczej (masz znaleźć minimalną, nie maksymalną) - wydaje mi się jednak, że to rozwiązanie również się sprawdzi.

Poradziłem sobie, dzięki wszystkim za pomoc bardzo dużo mi to dało. ;)

Po wczytaniu danych do tablicy wystarczyło zastosować 2 pętle for oraz jedną if. Gdzie n- ilość danych w górnej podstawie trójkąta.

int sum1,sum2;
  for(int i=n;i>=0;i--){
     for(int j=0;j<n;j++){
        sum1=A[i][j]+A[i+1][j];
        sum2=A[i][j]+A[i+1][j+1];
        if(sum1<sum2){			// Warunek wielkosci sumy
            A[i][j]=sum1;
        }
        else{
            A[i][j]=sum2;