Mam do rozwiązania problem znajdywania maksymalnej sumy podtablicy tablicy 2D, tyle, że mając na wejściu do dyspozycji znany rozmiar poszukiwanej podtablicy, czyli szukanie największej podtablicy o rozmiarze HxW w tablicy 2D o rozmiarze IxJ. Zrobiłem to metodą brute force (po prostu "chodzę" po tablicy kwadratami o wymiarach 2D, sumuję i porównuję ze zmienną i jak większa, to zastępuje, jak nie, to nie), ale muszę zrobić jeszcze drugą metodą optymalną. Jakieś rady, pomysły? Czytałem o algorytmie Kadane, ale chyba w tym wypadku to nic nie da. A może sumy prefiksowe? #programowanie #algorytmy
@drakerc: a jak by ten problem zamienić w szukanie najmiejszej podtablicy jakoś? wtedy w czasie n szukasz największego elementu i potem to już wiedząc możesz szybciej chodzić tak mi się wydaje
@drakerc: ale dam ci radę by zaalokować całą tablicę w jednym Ciągłym fragmęcie pamięci (w sumie system z procesorem i tak zrobią z tego kebab ale jest szansa że mniejszy)
@drakerc: A jakby pokombinować coś z dzieleniem macierzy na podmacierze, ale większe niż HxW, obliczanie sumy ich elementów i przewidywanie, gdzie może znaleźć się szukana podmacierz HxW?
Dla losowych danych styknęło. Ale jakby cała podmacierz zawierająca szukaną była np. złożona w większości z 1, a inna podmacierz byłaby normalna - to mój pomysł zawodzi.
Ale może nakieruje Cię to na jakieś lepsze rozwiązanie :)
w tablicy 2D o rozmiarze IxJ. Zrobiłem to metodą brute force (po prostu "chodzę" po tablicy kwadratami o wymiarach 2D, sumuję i porównuję ze zmienną i jak większa, to zastępuje, jak nie, to nie), ale muszę zrobić jeszcze drugą metodą optymalną. Jakieś rady, pomysły? Czytałem o algorytmie Kadane, ale chyba w tym wypadku to nic nie da. A może sumy prefiksowe?
#programowanie #algorytmy
wtedy w czasie n szukasz największego elementu i potem to już wiedząc możesz szybciej chodzić tak mi się wydaje
(w sumie system z procesorem i tak zrobią z tego kebab ale jest szansa że mniejszy)
Dla losowych danych styknęło. Ale jakby cała podmacierz zawierająca szukaną była np. złożona w większości z 1, a inna podmacierz byłaby normalna - to mój pomysł zawodzi.
Ale może nakieruje Cię to na jakieś lepsze rozwiązanie :)
źródło: comment_TtIB1DIgfSA1pblYylvwAAc39ypPvRPw.jpg
PobierzKomentarz usunięty przez autora
@drakerc: Wydaje się, że to zadziała: https://www.matematyka.pl/260564.htm