A megoldás algoritmusa
Ez a feladat nagyon hasonlít
Fazekas feladathoz. A megoldásban csak a
Best() függvénynek azt a ciklusát kell megváltoztatni, amelyik végigpróbálgatja, hogy hány tárgy kerüljön be a következő körben a kemencébe. Ez az előző feladatnál
K darab volt, itt viszont számolni kell a bekerült tárgyak tömegét, és akkor kell megszakítani a ciklust, amikor a következő tárggyal már
K fölé nőne az össztömeg.
Memória korlátok
Legfeljebb 10.000 darab tárgy lehet. Az égetési idő 1 byte, a súly 2 byte, a choice[] tömb tárgyanként 2 byte, mert legfeljebb 1000 tárgy kerülhet egyszerre a kemencébe. A cache[] tömb egy elemének pedig tudnia kell tárolni a lehető leghosszabb égetési időt, ami (K = 1, minden égetési idő = 100, minden tömeg = 1 esetén) legfeljebb 1,000,000 azaz 4 byte. Ez összesen legfeljebb (1+2+2+4)x10,000 = 90,000 byte, ez sajnos nem fér bele a Turbo és Borland Pascal 64 kilobájtjába.
A legegyszerűbb megoldás erre az lehet, hogy meghívunk egy eljárást, és annak egy helyi változója az egyik tömb, így az az adat a 64 kbyte-os stack-re kerül. (Ekkor viszont már a rekurzióra valószínűleg nem lesz elég hely.)
Megjegyzés:
Egy bonyolultabb megoldás lehet a cache[] tömb kiküszöbölése a choice[] tömb segítségével. A choice[] tömb kitöltött része ugyanis tartalmazza azt az információt, hogy egy adott i indextőtl kezdve milyen csoportosításban kell betenni a tárgyakat az optimális időhöz, de ebből már megkapható az optimális idő, azaz cache[i].
Ezzel a futási időt legfeljebb N-szeresére növeljük, mert a choice[] tömb is legfeljebb N elemű. Ezt mi nem próbáltuk ki...
Megoldások
