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
- Új 2K Gamer PC Ryzen 5 9600X/RTX 3070 Ti 8Gb/2x8Gb DDR5 6000Mhz/500Gb NVME SSD/2-3Év gari
- Asztali PC , R5 8400F , RTX 3070 , 16GB DDR5 , 512GB NVME , 1TB HDD
- Intel Core i9-14900K - Cores x 24
- Új Gamer PC Ryzen 5 9600X/RTX 3060 12Gb/2x8Gb DDR5 6000Mhz/500Gb NV3 NVME SSD/2-3Év gari
- Újszerű garanciális Dell Precision 3580 i7 1370p/32GB DDR5/1TB/RTX A500/100%sRGB
- BESZÁMÍTÁS! Sony PlayStation 4 PRO 1TB fekete játékkonzol garanciával hibátlan működéssel
- GYÖNYÖRŰ iPhone 13 Pro 128GB Graphite -1 ÉV GARANCIA - Kártyafüggetlen, MS3083
- GYÖNYÖRŰ iPhone 11 128GB White -1 ÉV GARANCIA - Kártyafüggetlen, MS3520, 100% Akkumulátor
- Bomba ár! Dell Latitude E7440 - i5-4GEN I 8GB I 500GB I 14" HD I HDMI I Cam I W10 I Gari!
- LG 32UN880P - 32" IPS ERGO / 4K UHD / 60Hz 5ms / DisplayHDR 400 / USB Type-C / AMD FreeSync
Állásajánlatok
Cég: PCMENTOR SZERVIZ KFT.
Város: Budapest
Cég: Laptopműhely Bt.
Város: Budapest