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? :-)

Hozzászólások

É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.

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.

“The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.”

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

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!.

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.

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.