Aktív témák
-
Spyx
tag
nem tépted feleslegesen az újjad. ez nem lenne rossz ötlet de kicsit hosszú a futási ideje.
egy rekurzív algoritmus is jó lehet mert az utólag át lehet alakítani dinamikus programozási megoldássá.
egyébként addig én is téptem az ujjam és már közel járok egy lehetséges megoldásnál már csak néhány kódolási hibán kell átrágnom magamat és kideül a tesztelésnél hogy fölösen dolgoztam -e ezzel a módszerrel
De addig is kössz hogy rászántad magad hogy segíts! :DD -
Miracle
senior tag
ez egy elég komoly játékelméleti probléma, nem foglalkoztam vele komolyan, csak olvastam valahol, és nem vagyok a dolgomban biztos, de úgy emlékszem, hogy az ilyen problémákra csak az összes eset végigpróbálgatása után lehet _tökéletes_ megoldást adni, de vannak megoldási stratégiák, amelyek nem adnak tökéletes megoldás, de az esetek nagyrészében jó megoldát adnak. sajnos nem emlékszem, hogy hol olvastam, de még egy problémára is emlékszem, ami ilyesmi volt, és a szerző 4 algoritmusra is adott olyan bemenetet, amivel nem a legjobb eredményt hozta ki. bár nem ugyan ez a probléma volt.
szóval nekem lenne egy ötletem egy egy lehetséges algoritmusra, ami nem tudom, mennyire hatékony, Cben szerintem meg lehet oldani, és azt sem tudom, helyes-e, azaz mennyire ad jó megoldást, az a gyanúm, hogy megfelelő bemenetel meg leht sz*patni, de általános esetben szerintem nem olyan rossz eredményt ad:
1: eltárolod a bemenetet egy szép nagy structokból álló tömbben, és kiszámítod a fajlagos haszon-arányát mindnek, (haszno/végrehajtási idő) rendezed
2: fentről elindulsz lefelé, mindent úgy illesztesz be(az idő-tömbödbe, amiben nyilvántartod, hogy melyik időegységek foglaltak, és melyik task van ott), hogy éppen a határidejére érjen véget.
3: ha amit be akarsz szúrni, és valahol ütközik, akkor agy rekurzív algoritmus megpróbál helyet csinálni neki, azaz
----ha a a végrehajtási idő jobb oldalán ütközik, akkor balra tolja, hogy beférjen,
----ha a végrehajtási idő a bal oldalán ütközik, akkor a már ott lévőt tolja balra, hogy ne ütközön,
----ha elfed egy másikat, akkor a másikat megpróbálja balra tolni
----ha egy már ott lévő teljesen elfedi, akkor az új elemet próbálod meg balra tolni
----ha több elemmel ütközik, akkor
a: hagyod a francba
b: megpróbálod balra tolni azokat, amik ütköznek, ha van közöttük
időrés, ha nincs, akkor az új elemet próbálod
meg balra tolni
szerk: vége, ha végigment a fajlagosan rendezett bemeneten.
szerk: a balra tolás az időben előbbre helyezést akarja jenenteni, vizuális típus vagyok, egyből elképzeltem.
a különböző eltolásokat ugyan ez a beszúrófüggvény intézi, így ha a beillesztés miatti eltolás ütközést okoz, akkor értelem szerűn az először eltolt elemnek is megpróbál helyet csinálni a fent említett módon, kell viszont egy rekurzió-szint korlát, mondjuk hogy max 5ször hívhatja meg magát, ezt egyszerű beépíteni, és visszatérési értékben szépen benne lehet, hogy sikerült-e a beszúrás, és ha igen, akkor a tömb marad, ahogy van, ha nem, akkor a rekurzió minden szintje visszarendezi, amit eltologatot, és visszatér egy hamis értékkel.
na ez egy kicsit bonyolult.
eszembe jutott mégegy:
egy parciálisan rekurzív függvény ami ha X időig rendezve vagyunk, akkor megnézi, mely taskok járnak le a legközelebb, és megpróbál z időnyit (vagy k tasknyit) előre feltölteni, ezen a z időn belül kipróbál minden lehetséges esetet, és a legjobbnak az _első_ elemét teszi bele a végeredménybe, majd megin megpróbál az utóbb betett task lejártától előrelátni.
az utóbbit szerintem sokkal egyszerűbb lekódolni, de az előbbi megérzésem szerint jobb eredményt ad. bár sokkal nehezebb.
persze lehet, hogy van tökéletes hatékony megoldóalgoritmus is, de azzal én nem szolgálhatok, ha nem sikerül olyat találni, akkor remélem segítettem valamit ezzel a két lehetőséggel.
[Szerkesztve] -
Spyx
tag
Azért nem volt jó az előző mert ott más volt a kérdés. De ha valakit nagyon zavar az hogy ennyi topicot nyitogatok akkor boccs.
A megvalósítást úgy értem ha már volna egy algoritmusom azt le tudnám kódolni de még az sincs.
futási idő: annyi egységnyi időt kell futnia egyfojtában mielőtt a befejezési időt eléri
nem kell végrehajtani mindet csak annyit és azokat hogy a nyereség maximális legyen.
PL.:
be:
2 3 60
3 4 100
2 4 60
ki:
[1 , 3] { azért az 1. és a 3. hajtjuk végre mert így 120 a haszon és ha esetleg a 2.-at hajtanánk végre nem jutna idő a másik kettőre}
Remélem nem voltam nagyon zavaros -
steveetm
őstag
Az előző topic erre miért is nem volt jó?
Ha meg tudod valósítani akkor mi a gond?
És a feladat se tiszta, mivan ha nem jut sorra az adott feladat amire be kell fejezni?
Mit kell kiiratni? Az ok hogy amit végrehajtunk, de egy ütemező végrehajt mindent, csak ütemezi őket ugyebár. Nem inkább végrehajtás sorrendje akar ez lenni?
A futási idő-t hogy kell értelmezni? Ha egyszer nekikezdesz a feladatnak az az idő egybe telik el, vagy csak egy ''ütem'' vonódik le?
Üdv.: steveetm -
Spyx
tag
Egy kötelező iskolai program megoldásához kellene segítség.
probléma:
egy tömben vannak letárolva az egyes feladatok egy számhármassal ábrázolva
1 elem: futási idő
2 elem: legutolsó befejezési idő(ameddigre kész kell lennie)
3 elem: haszon az adott feladat végrehajtásakor
Az feladatok befejezési idő szerint rendezve vannak.
kimenet: azon feladatok indexeinek kiiratása egy egydimenziós tömbe amelyeket végrehajtunk. Úgy kell kiválasztani a végrehajtandó feladatokat hogy minél nagyobb hasznot érjünk el. Ha több maximális megoldás van akkor is csak egyet kell megadni.
Nem kész programot kérek. Az algoritmus a lényeg azt már én meg tudom valósítani(elvileg). Vagy ha valaki tud szakirodalmat az is jó van időm átböngészni.
Előre is kössz!!
Aktív témák
- Gaming notebook topik
- sziku69: Szólánc.
- Luck Dragon: Asszociációs játék. :)
- sziku69: Fűzzük össze a szavakat :)
- Intel Core Ultra 3, Core Ultra 5, Ultra 7, Ultra 9 "Arrow Lake" LGA 1851
- Bambu Lab 3D nyomtatók
- FOTÓS beárazás
- A nagy Szóda, Szódakészítés topic - legyen egy kis fröccs is! :-)
- Milyen videókártyát?
- Vírusirtó topic
- További aktív témák...
- Féláron eladó vadonatúj razer blade 14 rtx 3080ti
- 500 ezerrel ár alatt! Vadonatúj garanciás razer blade 16 oled kijelző rtx 4070
- Hardverapró árérték bajnoka! Razer blade rtx 3080 ti i9 32gb ddr5 4k kijelző 144hz!
- Eladó kiskergaris 18TB-os Seagate EXOS X18 Enterprise HDD
- Félkonfig // I7 7700, GTX 1070, 16 GB DDR4
- ÚJ Lenovo ThinkPad X13 Gen 5 - 13.3" WUXGA IPS - Ultra 5 135U - 16GB - 512GB - Win11 - 2,5 év gari
- Bomba ár! HP EliteBook 820 G2 - i5-5GEN I 8GB I 256GB SSD I 12,5" FHD I Cam I W10 I Garancia!
- ÁRGARANCIA!Épített KomPhone Ryzen 5 7600X 32/64GB RAM RTX 5060 Ti 16GB GAMER PC termékbeszámítással
- Új elekrtomos rollerek 2/3 áron és e-bike dobozban, 1 év garanciával:
- Gamer PC-Számítógép! Csere-Beszámítás! Ryzen 5 8400F / 32GB DDR5 / RX 7800XT 16Gb / 1TB SSD!
Állásajánlatok
Cég: Laptopműhely Bt.
Város: Budapest
Cég: PCMENTOR SZERVIZ KFT.
Város: Budapest