Mohó algoritmus

Van egy ilyen izgi feladat:

https://leetcode.com/problems/house-robber/

Lényegében adott egy egész számokból álló sorozat,

és ebből úgy kell a maximális összeget kiválasztani, hogy nem választhatunk egymás melletti tagokat.

Először azt hittem, hogy ez rohadt bonyolult algoritmus lesz, mindenféle backtrackkel – és nem!

Csak kell hozzá egy másik sorozat, amelynek elemei így állnak elő n-ből:

m0 legyen n0

m1 legyen max(n0, n1)

ezen felül pedig m[i] legyen a maximuma n[i] + m[i-2]-nek és m[i-1]-nek.

Pl.

[1,6,6,9,7,1,8,1,8] esetére 31 a maximálisan elérhető érték,

6 9 8 8 |31

1 6 7 8 8 |30 csábító lenne pedig

Itt a segédsorozat (m):

1 6 7 15 15 16 23 23 31

A választ a segédsorozat utolsó tagja tartalmazza.

 

Érdekes lenne igazolni, hogy ez miért jó így? :-)

( wauf | 2021. 12. 01., sze – 14:36 )

Érdekes lenne igazolni, hogy ez miért jó így?

Formalisan nem bizonyitom, de te probalkozhatsz vele. Erre lesz szukseged: https://en.wikipedia.org/wiki/Loop_invariant

 

 

Az a gond a leetcode megoldasokkal amit talalsz a neten, hogy eles kodkent nem szabad oket a rendszerbe engedni, mert olyan valtozonevek mint i, n, m, stb nem hordoznak semmi lenyegi informaciot, a kodot csak az erti aki eloszor kitalalta. Aztan amikor a kod annyira bonyolult hogy mar o sem erti, akkor szokas ujrairni egesz rendszereket. Brrr.

 

n helyett legyen loot_in_houses

m helyett legyen best_loot_so_far

 

Igy mar azonnal trivialis hogy mi a fene az m tomb, es hogy ha hozzaadunk egy uj elemet, akkor az vagy az elozo legjobb zsakmany (amit te m[i-1]-nek hivtal), vagy a jelenlegi hazban talalhato zsakmany (n[i]) es az elozo elotti legjobb zsakmany osszege (m[i-2]). Azert elozo elotti, mert akkor kihagyjuk az elozo legjobb hazat, mert ami mellette van abbol tobbet rabolhatunk.

( harlequin | 2021. 12. 01., sze – 14:42 )

Hát, ha bizonyítod, hogy ha a lista az eddigi legjobb megoldást tartalmazza, akkor az új taggal is azt fogja (itt két lehetőséged van, szóval nem túl bonyi), és azt, hogy a list a 1.-2.-3, tagja a legjobb megoldást tartalmazza (ezt meg manuálisan lehet), akkor ezzel megvagy.

“Any book worth banning is a book worth reading.”

( AszaltSzilva | 2021. 12. 01., sze – 16:54 )

Ezért kellett volna a teljes indukcióról tanulni a középiskolában, vagy még az általánosban.

Mikor érdemes az utca utolsó házát kirabolni? Ha az utolsó előtti nélkül, meg a mostanival többet szedek össze, mint ha ezt kihagyom és az utolsó előttiig rabolok. f(n)=max(x_n+f(n-2), f(n-1))

A dinamikus programozás arról szól, hogy a rekurziót - amit az előbbi meggondolás tartalmaz - átírjuk ciklusra, és ehhez nyilvántartjuk, hogy az 1...k házszámú házakból mennyi zsákmányolható. Ezt - az összeget - tartalmazná a dp[k] elem. 

Általános iskolai versenyeken az utca hossza rendszerint már akkora, hogy a rekurzió már lassú néhány tesztesetnél (exponenciális bonyolultság), míg a dinamikus programozás (lineáris bonyolultság) nevetve megold mindent.

AL

( mraron | 2021. 12. 01., sze – 17:14 )

Két variációja a feladatnak ha valaki szereti az ilyet:

Ha azt akarjuk hogy a kiválasztott házak közötti távolság legalább L legyen (tehát pl. a mostani feladatra L=2).

Ha azt akarjuk hogy a kiválasztott házak közötti távolság legalább L és legfeljebb R legyen. Ez már egy kicsit nehezebb, aki lineáris időben meg tudja oldani azt meghívom egy virtuális sörre :D

Ha van hozzá energiád, megoszthatnád az ötleted:
Please file this topic on our content-issue Github repo here to be eligible rewards: https://github.com/LeetCode-Feedback/LeetCode-Feedback/issues/.
We opened this Github repo specifically for ideas like the one you brought up and other content-issues listed in here: https://leetcode.com/discuss/general-discussion/526802/File-Problem-and-Solution-Content-Issues-to-Our-GitHub-Public-Feedback-Repo-Now!.

( szz v | 2021. 12. 01., sze – 18:22 )

Amúgy imádnivaló ez a leetcode. Szerintem minden programozónak érdemes lenne 1-2 naponta rászánnia magát, hogy a napi feladatot (https://leetcode.com/problemset/all/) megnézi – vagy itt, vagy egy másik hasonló oldalon. Oly sokszor volt olyan helyzet, hogy a megoldásokból volt mit tanulni...

Eddig én sem ismertem ezt az oldalt, felvettem a listámba.

Én viszont rengeteget tanultam a https://www.codewars.com/ oldal példáiból. A "8 kyu" tényleg a pár perces belépő. Aztán lejjebb haladva jönnek az elgondolkoztatóbbak.
A legjobb, hogy végigszenveded és ha a publikus és nem publikus tesztvektoron átmegy, akkor szépen megnézed hogy a többiek dobtak-e be frappánsabb megoldást.

( szz v | 2021. 12. 03., p – 09:16 )

A mai leetcode (értsd: e-leet code) feladat zseniális: https://leetcode.com/problems/maximum-product-subarray/ Annyira egyszerű a feladat, hogy egy harmadikos általános iskolás is megértheti. (Össze is hoztam egy 8372 ms-os futást, ami az elfogadható kategórián belül volt.) Az igazán profi megoldás egyáltalán nem triviális. Ilyet mutat be Timothy H Chang: # https://www.youtube.com/watch?v=q3Q-2a8NnCQ – ez 52 ms alatt futott le.