- This topic has 8 hozzászólás, 5 résztvevő, and was last updated 21 years, 6 months telt el by
.
-
Bejegyzés
-
Hmm, asszem ez egy jó kis MI feladat. Csak a nyers erõ megoldását ismerem, O(n!) így elsõ ránézésre. Fel kell írni az összes lehetséges kombinációt, majd a maximumok összegének a minimumát kell keresni. Bár mivel soros a végrehajtás, a gráfok körül tett kalandozással úgy o(n^2)-re le lehet vinni a végrehajtási idõt. Persze lehet hogy van vmi O(n) megoldása is, de öt perc után ez nem megy nekem, estleg egy kicsit késõbb megnézem.
A nyers erõ biztos nem jó mivel 1 másodperc és 16m memória korlátozás is van benne. Ez 10000 elemnél már eléggé komoly akadályt jelent.
Alapvetõen ez a programozási feladat egy matematikai problémára épül. Gondolom prog. mat. szakon adnak ilyen feladatot.
Jól gondolod, bár ez a feladat a Nemes Tihamér versenyen is fel volt adva igaz ott a döntõben. Ez alapján feltételezhetõ, hogy mélyebb matektudás nélkül is megoldható. (Bár nem tudom milyen emberek jutnak el egy ilyen verseny döntõjébe)
A megoldás azért érdekel, ha rájössz írd meg légyszi…Az égetésre váró tárgyakat az érkezésük sorrendjében kell kiégetni.
Ez egy elég rafinált megjegyzés… nemde?
😀Kapacitásnyit bepakolok, aztán a legnagyobb égetési idõket összeadom.
Igaz így lehet, szénné ég pár edény, ha túlégetik a kemencében…
😉] Kapacitásnyit bepakolok, aztán a legnagyobb égetési idõket összeadom.
Túl egyszerû, úgyhogy biztosan nem.
például: idõk=1, 2, 3 kapacitás=2 esetén:
2+3 lenne az idõ így, pedig az optimum 1+3 lenne.
… jó-jó, egy agyag edény azért ritkán ég szénné.
Rendezd sorba, égetési idõ szerint csökkenõbe… és a soron következõ kapacitásnyit pakold be mindig a sütõbe.
Aztán 1 kapacitásnyi esetén optimalizáljál, szakikám. 😀6,3,3,2,1
4 kapacitás esetén
6+1 = 73 kapacitás esetén
6+2 = 82 kapacitás esetén
6+3+1 = 10Hello!
Tudja valaki ennek a problémának a megoldását?
Egy fazekas mûhelyében sorban várakoznak a kiégetésre váró tárgyak. Minden tárgyról tudjuk, hogy mennyi az a legkevesebb idõ, ami a kiégetéshez kell. Az égetésre váró tárgyakat az érkezésük sorrendjében kell kiégetni. Egyszerre több tárgyat is rakhatunk a kemencébe, azonban legfeljebb annyit, amennyi a kemence adott kapacitása. Az égetési idõ egy menetben mindig a kemencébe rakott tárgyak minimális égetési idejének a maximuma kell legyen.Feladat:
Készíts olyan programot (FAZEKAS.PAS vagy FAZEKAS.C), amely kiszámítja, hogy legkevesebb mennyi idõ kell az összes tárgy kiégetéséhez, továbbá megadja azt is, hogy ezen idõ eléréséhez mely tárgyakat kell egy-egy menetben a kemencében együtt égetni.
Bemenet:
A FAZEKAS.BE állomány elsõ sora két egész számot tartalmaz; a tárgyak N (1<=N<=10000) számát és a kemence K (1<=K<=100) kapacitását. A következõ N sor mindegyike egy pozitív egész számot tartalmaz; a tárgy minimális égetési idejét, ami nem nagyobb, mint 200. Kimenet: A FAZEKAS.KI állomány elsõ sorába az összes tárgy kiégetéséhez minimálisan szükséges idõt kell írni. A következõ sorok mindegyikébe két egész számot, I-t és J-t kell írni egy szóközzel elválasztva, I az elsõ, J pedig az utolsó tárgy sorszáma, amelyek egyszerre kerülnek a kemencébe. Példa: FAZEKAS.BE
7 3
10
8
20
25
30
12
40
FAZEKAS.KI
75
1 2
3 4
5 7
- Be kell jelentkezni a hozzászóláshoz.
legutóbbi hsz