Algoritmus
Backtrack
Megjegyzés: Csak az 5. tesztesetre nem fut le időn belül. Tehát végeredményben, ha DP nem sikerül, akkor ahogy mindig hagyatkozhatunk a backtrackre is.
Rendezzük a dolgokat súly szerint növekvő sorrendben (mert így ha $x.$ elemet nem tehetjük be, akkor az $x+1$-et már nem is vizsgáljuk.). Nyomon követjük, hogy eddig mennyi a tárgyak összsúlya, és ha még befér a teherautóba akkor betesszük az indexét (a rendezett tömb szerinti) egy listába, ha nem akkor elmentjük, hogy az adott összsúlyhoz milyen tárgyakat tudtunk betenni. Ha betehettük, akkor a következő elemet vizsgáljuk, ha nem, akkor kivesszük a legutolsó betett elemet a listából és az ő indexének+1. elemmel folytatjuk a vizsgálatot.
Ha az algoritmus során egy olyan esetet találnánk, ahol az összsúly éppen a kamion kapacitása, akkor befejezzük az algoritmust és örülünk a megoldásnak.
Egyébként pedig akkor áll le az algoritmus, ha az utolsó elemet is kivettük a listából, és az $N+1.$ elemet szeretnénk betenni, ami nem létezik.
Ha az algoritmus során nem találtunk olyan megoldást, ami telerakja az autót, akkor szépen elindulunk lefelé és addig megyünk amíg megtaláljuk a legnagyobb betehető összsúlyt. Ha megvan, akkor lekérjük a hozzá tartozó tárgyak eredeti indexét.
Dinamikus programozás aka. DP
Valahogy érezzük a DP-t, csak meg kell fogni ;). Először is ki kell találnunk egy frappáns rekurziót, amire automatikusan megy a DP-vé "okosítás". Hasonlóan a buta-algoritmushoz itt is rendezünk, hogy ezáltal is "gyorsítsunk".
Legyen a rekurzív függvényünk olyan, ami megmondja, hogy egy adott elemtől indulva (a rendezett tömbben), mennyi a minimuma a $K-\mbox{max. összsúly}$-nak, ha tudjuk, hogy még ennyi súly fér bele. Nyílván $\mbox{rekurzív függvényünk}(1, K)$-el indítunk, hiszen először az összes elemet vizsgáljuk és még $K$ súly fér bele a kamionba (hiszen üres). Hogy néz ki maga a rekurzív függvény?
Tehát adott a függvényünknek, hogy honnantól vizsgálja az elemeket, illetve még mennyi fér a kamionba. Nyílván ha az összes elemet végignéztük, tehát $N+1.$ elemet szeretnénk visszatérni, akkor a függvényünk a "még mennyi fér a kamionba" tér vissza, hiszen ennyi üres hely maradt. Ha belefér a vizsgálandó tárgy a kamionba, akkor két részre bomlunk: betesszük, nem tesszük, és a két eset által adott eredmény minimumával térünk vissza. Ha betesszük, akkor $(i+1,\mbox{maradék}-\mbox{betett súly})$-re hívjuk meg a függvényt (ahol $i$, az adott elem, amit vizsgálunk), ha nem akkor pedig $(i+1,\mbox{maradék})$-ra. Ha nem fér bele a vizsgálandó tárgy, akkor pedig a $\mbox{maradék}$-kal térünk vissza, hiszen ez az ág befejeződött.
Ehhez a DP hozzáadása a következő: csinálunk egy két dimenziós tömböt, aminek az indexei a függvény argumentumai és ha még nincs az adott érték eltárolva, akkor számolunk és eltároljuk, különben pedig csak az eredménnyel tér vissza a függvény (ezt hívjuk Fehér Gábor után szabadon cache-nek.) Ez szép és jó, de ezzel csak a max. összsúlyt tudjuk meghatározni, azt is tudnunk kell, hogy mit tettünk be a kamionba. Ehhez egy choice-ot használunk, jelen esetben ez egy két dimenziós tömb, melynek elemei listák. A tömb indexe pedig hasonlóan az előzőekhez a függvény argumentumai. A cache-el ellentétben ez "hátulról" fog feltöltődni, hiszen ahogy térünk vissza a rekurzió mélyéről, úgy tudjuk feltölteni a listát, hogy mit tettünk be. Minden egyes betétel (tehát amikor úgy döntünk, hogy betesszük a tárgyat a kamionba) esetén betesszük a listába ($\mbox{choice}[i, \mbox{maradék}]$-ba) az elemet, de előtte betesszük az eddig betett elemeket (amik vagy a $\mbox{choice}[i+1, \mbox{maradék}]$, vagy az $\mbox{choice}[i+1, \mbox{maradék}-\mbox{betett súly}]$ listában vannak). Ha nem tettük be az adott tárgyat, akkor csak átmásoljuk az elemeket. Végeredményben a megoldást, azaz, hogy akkor pontosan miket kell betenni a $\mbox{choice}[1, \mbox{max. összsúly}]$-ban találjuk.
Kódok
Főoldal
>
Versenyek
>
Nemes Tihamér OKSzTV
>
2008
>
Második forduló
>
11-13. osztály
>
Pakolás
>
Megoldás
