Aktív témák

• #14 khalox őstag Spyx #13

  2004-10-22 17:39:40 #14

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  khalox

  őstag

  válasz Spyx #13 üzenetére

  Igaz, akkor branch&bound... (korlátozás és szétválasztás, vagy hogy a frászba hívják magyarul - lehet, hogy sehogyse hívják).
  
  [Szerkesztve]

• #13 Spyx tag khalox #12

  2004-10-22 14:02:45 #13

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Spyx

  tag

  válasz khalox #12 üzenetére

  Mohó algoritmus nem jó mert itt maximalizálni kell a hasznot. próbáltam nagyon kevés esetben ad jó megoldást a mohó keresés

• #12 khalox őstag Spyx #11

  2004-10-22 13:36:15 #12

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  khalox

  őstag

  válasz Spyx #11 üzenetére

  Ilyet keress, hogy 'mohó algoritmus', na az kell neked.

• #11 Spyx tag heihachi #10

  2004-10-22 13:34:30 #11

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Spyx

  tag

  válasz heihachi #10 üzenetére

  2 :amikorra kész kell lennie . csak akkor vegyük bele a feladatot ha a befejezési idő előtt kész lesz. ha azzal nagyobb hasznot érünk el akkor inkább másik feladatok elhagyásával szórítsunk helyet az aktuális feladatnak

• #10 heihachi addikt Spyx #3

  2004-10-22 12:57:43 #10

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  heihachi

  addikt

  válasz Spyx #3 üzenetére

  Én ezt nem értem. Jó kis feladatnak tűnik, de nem értem.
  Van három érték:
  1 - futási idő
  2 - ????
  3 - hasznosság
  
  Az ok, hogy maximális legyen a hasznosság, de mennyi futási időnk van?

• #9 Miracle senior tag Spyx #8

  2004-10-22 01:17:46 #9

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Miracle

  senior tag

  válasz Spyx #8 üzenetére

  ha nem ment fölösbe' akkor szívesen, örültem, hogy segíthettem :)
  szerk: és kíváncsi vagyok a te megoldásod eredményére, meg az algoritmusoda. Persze csak ha nem titkos.
  
  [Szerkesztve]

• #8 Spyx tag Miracle #7

  2004-10-22 00:55:18 #8

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Spyx

  tag

  válasz Miracle #7 üzenetére

  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

• #7 Miracle senior tag

  2004-10-22 00:30:06 #7

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Miracle

  senior tag

  várjá' jól vágom(most táttam a másik topicot,a z eddig ignoráltam), hogy ezt pascalban szeretnéd? és hogy nem nagyon mennek a bonyolultabb dolgok? meg hogy távol áll a lelked egy rekurzív függvénytől is? akkor most feleslegesen téptem az ujjaimat :(

• #6 Miracle senior tag Spyx #5

  2004-10-22 00:19:17 #6

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Miracle

  senior tag

  válasz Spyx #5 üzenetére

  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]

• #5 Spyx tag Miracle #4

  2004-10-21 23:30:09 #5

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Spyx

  tag

  válasz Miracle #4 üzenetére

  max 3000 feladat van a bemenetben. Ez igencsak sok.
  egyébként az egész proginak 1másodpercnyi futásiídő van limitálva(ez a gázos) és 16MB memórialimit.

• #4 Miracle senior tag

  2004-10-21 23:24:41 #4

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Miracle

  senior tag

  Van valamilyen korlát futási időre, memória használatra? mekkora bemenő adathalmazra kell mennie?
  ha mondjuk 10000 task közül kell választani, akkor gázos, de ha csak pár*10 akkor van egy lehetséges(bár nem hatékony megoldás-ötletem)

• #3 Spyx tag steveetm #2

  2004-10-21 23:09:08 #3

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Spyx

  tag

  válasz steveetm #2 üzenetére

  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

• #2 steveetm őstag Spyx #1

  2004-10-21 23:02:06 #2

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  steveetm

  őstag

  válasz Spyx #1 üzenetére

  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

• #1 Spyx tag

  2004-10-21 22:48:16 #1

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  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