Fórumok
Sziasztok!
Az alábbi feladatot szeretném megoldani, C# nyelven objektum orientáltan.
Tudnátok segíteni abban, hogy a beérkező pályázatokat mi alapján lenne érdemes rendeznem / válogatnom / a tömböt bejárnom, hogy a lehető legnagyobb összes bevételt érjem el a végén? Több ötletem is volt már, de egyik se működött rendesen minden bemeneti fájl esetén.
Minden észrevételt/javaslatot szívesen fogadok!
Köszi előre is a segítséget.
Hozzászólások
Szerintem prog.hu-ra való téma, ez a HUnixP. De majd @tray kijavít.
Azt láttad ugye hogy melyik fórumtémában járunk? Na, ennek a létezése trey válasza.
--
Jogos, mea-culpa. Adtam választ is kérdező problémájára.
És még Trey nevét is elrontottam. 2xsorry
Legalább elolvastad a kérdést, vagy csak ráugrottál néhány buzzwordra?
----------------
Lvl86 Troll, "hobbifejlesztő" - Think Wishfully™
A kenőpénzek és a pártkötődések kimaradtak az inputból? :)
Amúgy a knapsack problemhez hasonlít, onnan talán lehet ötletet meríteni. Ja meg gráfelméletből a maximal independent set.
--
LICIT.BE fájlban lévő negatív ajánlati árak jelzik a kenőpénzt. Az algoritmus persze ABS() függvénnyel használja az értékeket, de az eredményben normál értékben jelenik meg.
Jaja, eléggé hátizsák problémának tűnik. Annó mintha az egyik évfolyamtársam kapta volna beadandónak. És ő mintha az egységárak alapján rendezte volna csökkenő sorrendbe. (Hogy végül hány pont lett, azt passzolom.)
Szóval úgy néz ki, hogy a kérdés analóg a maximum weighted independent set probléméval. Akkor válasz az eredeti kérdésre: a probléma egy gráf, a licitek a csúcsok, az egymást ütő licitek az élek, a csúcsok súlya a licitek értéke. Gráf ábrázolásra sokféle módszer van, van jobban és kevésbé oop-barát is, célszerű az algoritmushoz választani elsősorban.
--
Ahogy én nekiállnék:
0. Adatok beolvasására és kiírására egy OOP osztály. Ezzel a keret megvan.
1. OOP osztály a parcellák adatainak tárolására (0. lépésben töltjük fel)
2. Parcellák osztály (innentől az OOP részét találd ki Te)-ban a leadott pályázatok összes kombinációját (https://hu.wikipedia.org/wiki/Kombin%C3%A1ci%C3%B3) összeállítjuk.
3. Kombinációk: minden mindennel, sorrend nem számít = 1; 2; 3; 4; 1+2; 1+3; 1+4; 2+3; 2+4; 3+4; 1+2+3; 1+2+4; 1+3+4;
4. Kombinációk közül kiszűrjük a nem érvényeseket: ugyanazt a darabot akarják megvenni.
5. A kombinációk megmaradt halmaza egy-egy vásárlási lehetőséget jelent: minden kombinációnak van egy értéke, amely az ajánlati árak összege.
6. Erre kell egy maximum keresés (pl: eredmény = 12345Ft = 1+3+4)
7. 0. lépésben megírt osztály felhasználása az eredmény kiírására.
A 3. pont gyanús, n/m=100-nál nagyon el tud szállni a futásidő. Gyakorlatnak így is jó, de jól megcsinálni nem kezdő szint (és egyáltalán nem oop-n múlik).
--
Megelőztél és cizelláltabb voltál.
De okulásképp, hogy mire is kell ügyelni többek között, ahol algoritmusokat fejlesztenek emberek:
1. Algoritmizálhatóság. Algoritmizálható legyen lehetőleg a probléma. Azaz ne oldjon meg csempézhetőség eldöntést, vagy turing gépről ne döntse el, hogy lefut-e. Gondolj bele kódlefedettség tesztelésnél, van egy ilyen szubrutinod:
Akkor mi a szükséges feltétele a 100% lefedettségnek?
2. Sebesség. Ezt már vesézték többen is, lehetőleg ne exponenciális vagy NP-nehéz probléma legyen, vagy ha mégis az, érdemes jó, kitesztelt heurisztikákat alkalmazni, vagy approximációs algoritmusokat, vagy vegyesen, versenyeztetve
3. Stabilitás, pontosság. Gyakori probléma a folytonos lineáris programozási megoldó eljárások implementációjánál (is) a különböző adatstruktúrák ábrázolásából, műveletek elvégzésekor stb. keletkező többnyire kivédhetetlen hibák kumulációja, amely oly mértékű lehet, hogy akár az eredményt is befolyásolja nagymértékben, pl. lényeges eldöntendő kérdésre adandó választ billent (van-e megoldása ennek a feladatnak - nincs, de mégis ad a hibák miatt egy (fals) megoldást)
...
(n+1). minden más, amit kihagytam :)
Tipikus fogyatékos gányoló. mégy csak PSPACE-ben sem lesz a javasolt megoldásvázlat alapján a késztermék. Illetve néha PSPACE-beli marad, de nem PTIME-beli, ha a 3. és 4. lépés között van feedback, a legenerált "kombinációkat" egyenként ellenőrizzük, mielőtt érvényességét eldöntenénk. (n over floor(n/2)) aszimptotikája az exponenciális, úgyhogy így is rábasztál.
1 fortran kóder >>>>> 6 milió OOP fag
1 fortran kóder >>>>> 6 milió OOP fag
na, mert aztán a fortran kóderek sokkal jobbak az évtizedekkel ezelőtti szemléletmódjukkal - ami az adott korban, adott hardverre, adott fordító mellett jó volt, de azóta inkább káros, mint hasznos.
--
blogom
+1
És ez korrelál azzal, hogy...? :)
lehet én vagyok hisztis, de mintha régen olyan lett volna a szólás a zinterneten, hogy egy fórumban az elején meghúzod magad, s nem küldesz el senkit melegebb éghajlatra.
--
blogom
"A stílus maga az ember."
Megértem, ha a fenti megoldás szerinted gány, de nem szép, hogy a másik embert minősíted. Tartsd észben, hogy kezdőnek lenni nem tulajdonság, hanem állapot.
+1
Bár abban sajnos igaza van, hogy sokan megakadnak ilyen szinten, ami gáz - de ezt már teljesen elvonatkoztatva mondom, mindentől.
Csak azt hiányolom, hogy nem írta oda, hogy ez nem feltétlen alkalmazható algoritmust tartalmaz, de vázlatnak jó lesz, és nem szentírás, mert még az alkalmazott adatszerkezetekkel is elképzelhető, hogy trükközni kell. Ezen megjegyzések hiánya miatt trollkodásnak vettem.
Én legalább adtam egy példát :)
Enélkül, a többi - bevallom igaz és jó és helyen - hozzászólással a kérdező csak itt kötne ki: http://www.bethlen.hu/matek/mathist/forras/Graf_fogalma.htm
A feladat maga tipikusan a 10 évvel ezelőtt is oktatott Pascalos (sic!) szintű feladat. A megoldás módja pedig szintén ilyen szintű. Beadni floppy lemezen kell...
Minek ide gráf? Nem mondom, hogy nem alkalmazható, de nem feltétlen szükséges. Továbbá minek dobálózol matematikai fogalmakkal, amikor alapvető számítástudományi ismereteid sincsenek, a hozzászólásod alapján?
Egy kapcsolódó probléma: tegyük fel, hogy minden parcellaintervallumokra megajánlott összeg nemnegatív. Ekkor érdemes azzal a részfeladattal foglalkozni, hogy soroljuk fel az összes olyan intervallum kiválasztást, amelyben minden intervallumpár diszjunkt, és nem választható ki újabb, mindtől diszjunkt intervallum.
Ötlet arra, hogy hogyan válasszuk ki a kapcsolódó problémához tartozó, nem bővíthető kiértékelendő ajánlathalmazokat, mindegyiket pontosan egyszer:
- válasszuk ki külön-külön azon ajánlatokat, melyek bal végpontja nem nagyobb a legkisebb kiválasztható jobbvégpontú ajánlatnál, tovább diszjunkt minden eddig kiválasztott ajánlattól
- iteráljuk az eljárást úgy, hogy a legutoljára kiválasztott elem jobb végpontjánál nagyobb balvégpontú ajánlatokat fogadjuk csak el
- ha nem válaszható ki intervallum az eljárás alapján, akkor kiértékeljük a kiválasztott ajánlatok árainak összegét, és ha nagyobb, mint egy korábban kiválasztott érték, akkor ez lesz az új maximum
Egy optimális kiválasztás súlya így könnyen meghatározható a fenti ötlethez hasonló lépéseket tartalmazó rekurzióval. Nem állítom, hogy az eljárás optimális sebességű vagy pontosságú lesz.
Zavaró, hogy valaki 12 napos regisztrációval kissé arrogáns véleményt mond olyan emberekről, akiket nem ismer. :)
Be lehetne vezetni a próbaidőt, az első 10 komment alapján pl. :).
--
i need moar safe space!!4!44
<@dotnetlinux> A feladat maga tipikusan a 10 évvel ezelőtt is oktatott Pascalos (sic!) szintű feladat. A megoldás módja pedig szintén ilyen szintű. Beadni floppy lemezen kell...
> floki
> pacalos
vs
http://hup.hu/node/144182#comment-1932421
vs
ebay, jofosás, vakera flokilemez/flokiegység árak
Hmmm.
Egy feladat színvonalát mennyire befolyásolja az, hogy milyen nyelven van megoldva? Nem az a lényeg, hogy meg van oldva, c-ben/sh-ban/batchben/brainf!ckban? Mert pacalban sosem létezett olyan nehéz feladat, ami később elterjedtebb nyelveken is nehéz maradt, azért tartod színvonalon alulinak?
Ha meg bajod van a floppyval, vegyél goteket!
>Zavaró, hogy valaki 12 napos regisztrációval kissé arrogáns véleményt mond olyan emberekről, akiket nem ismer belenyomja az orromat a saját szaromba. :)
fix'd for you :)
Lehet, hogy nem vetted észre, de ez egy iskolai (!) feladat, kezdő programozás kategóriában, ahol a kérdező épp az OOP-t tanulja, talán tud procedurálisan programozni, de az sem biztos. A példafájlok, amiket mellékelt (és én is emléxem tanulmányaim alatt) maximum 5-10 sorosak. Nem itt kell a bigdata tapasztalatokat előhozni, azzal maradj a pénzkeresésnél.
Az operációkutatás mióta bigdata, egyáltalán milyen bigdata tapasztalatokról beszélsz? Idecitálsz egy ide egyáltalán nem való buzzwordöt, hogy majd emiatt leboruljak a nemzet nagysága előtt. Gyakran a kokány implementációk miatt kell bigdata problémákkal szembesülni a való életben, ez tény. Attól még, hogy iskolai feladat, állhat mögötte szép, mély matematikai probléma, mint jelen esetben is, és nem mellékes, hogy hogyan, milyen sebességű algoritmussal, milyen pontosságú algoritmussal oldjuk meg.
Mivel megvan határozva a bemenő adat max mennyisége, szerintem bármilyen nagyobb rugózás ezen a feladatom már overkill. Ha akarja, brute force -al is kikeresheti a tökéletes megoldást, mert az sem fut tovább 1-2 másodpercnél. Ráadásként ha már iskolai feladat, ezt a részét is lehetne pontozni. Nálam helyből 1-es, ha valaki egy faék egyszerűségű programot teljesen feleslegesen túlbonyolít. Programozóként, a munkám része az idő management is, így ha valamit felesleges megoldani szépen, mert csak 1x fogom használni, vagy a feladat meghatározza a felhasználás kereteit mint jelen esetben is, össze fogom rakni a legegyszerűbb módon. Mindent el lehet vinni, ezt a feladatot is, hogy hiperszuper algoritmussal csináljam, többszálon, cluster üzemben, de minek?
// Happy debugging, suckers
#define true (rand() > 10)
Hol? BTW. alaphalmaz hatványhalmazának fogalma megvan? És annak az elemszáma is megvan?
Christofides nevet ezen (lásd metrikus TSP approximációs megoldás)
a) Hint:
1 < N < 100 és 1 < M < 100
b) Lehet itt jönni a Christofides algoritmussal, de ezt a feladatot annyira faék egyszerűségűre le lehet hozni, hogy míg te az optimalizálásra törekedsz és keresed a tökéletes megoldást, a feladat kétszer befejezhető pure úton egy kevés cpu idő beáldozásával.
Lehet itt rugózni a dolgon, de teljesen felesleges. Az arroganciád részemről a mérhetetlen kategóriába sorolandó, de azért szép teljesítmény hogy másfél hét alatt elérted a troll szűrő alsó küszöbét
// Happy debugging, suckers
#define true (rand() > 10)
Nem kevés, hanem irdatlanul sok. És a ram sem lesz elég neki.
A christofides nem ide való, az TSP heurisztika, 3/2 approximációs faktorral, az előtte létező 2-es faktorút javította meg. Csak azért említettem, mert ott (is) érdemes volt reszelni a korábban ismert polinomiális idejű heurisztikákon. Itt meg pláne értelmes volna, mert szakértő ismerősöd alapból adott egy olyan algoritmus, melyre 100-as input méret esetén a világ összes ramja és cpu-ja nem lesz elegendő.
egy account, többségében szakmai hozzászólásokkal a hupon? wtf
„Tipikus fogyatékos gányoló. ”
azért az élet nem rózsaszín habostorta.
--
blogom
őszintén szólva nem nagyon zavar az ilyesmi :)
+1, a szakmai tartalom mindenért kárpótol
Pedig az én megoldásvázlatom csúnya, bohócmasnié szebb. Az enyimről azt sem tudom, hogy P-beli-e. Mások meg előbb pedzegették nálam, hogy a dotnetkirály megoldása triviálisan exponenciális futásidejű, sőt tárigényű - az enyim legalább PSPACE-ben marad.
A példafájl 5-10 soros, de a megoldásokat nagyobb adatmennyiségekkel is szokták tesztelni, illetve sarokesetekre készült adatokkal is. Általában úgy lövik be a teszt idejét, hogy aki nagyságrendileg lassabban fut az elvártnál (pl négyzetes helyett exponenciális algoritmussal) az timeout-ot kap és 0 pontot.
ha balról jobbra nönek a parcellák, és egy ajánlatot egy balrol jobbra menö súlyozott élnek tekintesz, akkor a maximális súlyú út jó lesz. ilyet meg mondjuk a Dijkstra ad (azaz a mohó algoritmus a parcellákon)
Szerintem kell hozzá egy kis kiegészítés: minden cellából a következőbe húzz be egy 0 súlyú élt. Enélkül nem garantált, hogy bejárható az egész.
--
Hogyan kell a Dijkstra-t mohó módon maximális útkeresésre alkalmazni ezen az inputon?
# cat LICIT.BE
3 4
1 2 2000
2 3 3000
3 4 2000
és ezen?
# cat LICIT.BE
3 4
1 2 1000
2 3 3000
3 4 1000
és ezen?
# cat LICIT.BE
6 8
1 3 2000
2 4 4000
3 5 5000
4 6 5000
5 7 4000
6 8 2000
"Ah! A problémára létezik megoldás! - és visszafekszik aludni."
minden parcellara rairod hogy mennyi penz szerezheto a szigoruan alatta levok ertekesitesebol.
ha egy parcella egy foglalas vegpontja felett van 1-el, akkor a foglalasrol optimalisan megallapithato, hogy be kell-e venni, hiszen a bevevesekor a koltsege ajanlat+m(kezdo_parcella), ha nem vesszuk be, akkor meg m(elozo_parcella)
tehat
m1=0
m2=0
m3=max(2000+m1,m2)=2000
m4=max(3000+m2,m3)=3000
m5=max(2000+m3,m4)=4000
like
Szép leképzése a problémának egy másik már ismert és diszkutált problémára!
A posztolónak javaslom, hogy általában is úgy szoktak működni a hasonló feladatok, hogy a tárgyhoz tartozó algoritmusok ismeretében meg lehet találni, hogy melyikre lehet leképezni a feladatot.
:-D :-D Az észrevétel jogos és valóban működni is szokott - de az is tény, hogy pont ebből adódóan a valós életben ilyen módon akkor sem lehet megoldást keresni.
sub
+1
A rendezésnek legfeljebb a futási időre szabadna hatnia, a megoldások számára nem. Küldenél néhány example input (és estleg output fájlt)?
szerk.: typo.
Mennyire sportszerű házi feladatot hupperekkel megoldatni?
Knapsack feladat speciális esete lesz a megoldás, mivel itt intervallumok vannak tetszőleges subset helyett. Erről hirtelen nem látom, hogy NP-nehéz vagy P-beli. Rekurzió vagy dinamikus programozás az, amit keresel.
Egyébként vamzerkodásra buzdítom a huppereket, ha valahol bevprog, elalk, progmod, opkut vagy egyéb tárgyból hasonló beadandó van, jelentse bátran!
Deadmau5t meg hallgassátok, mert jó https://www.youtube.com/watch?v=F0YYoo6oFoU
+1, már akartam én is írni.
Szerintem a knapsack nem kezeli az egymást kizáró dolgok közötti válogatást.
--
+1, szerintem se, szerintem is a maximális független ponthalmaz lesz a megoldás.
arra nem emlékszem, azt hogyan keresünk gráfban - főleg, ha az egyes csúcsokat más-más értékkel szeretnénk számolni.
De a hátizsák probléma nem erről szól.
--
blogom
jogos, de tipikus implementációnál, mint pl. gams, zimpl, ampl/gmpl stb. egy kategóriával több vagy kevesebb constraint az nem számít (de), és a való életben többnyire diszjunkt részhalmazokat választunk ki ;). Mindenesetre azt érdemes kihasználni, hogy diszjunkt intervallumokat kell kiválasztanunk, ezzel lényegesen gyorsítható a megoldás.
Semennyire, ebben egyetértünk.
Hogy mit is jelentsünk, hova? Szerintem a posztoló nem azt kérte, hogy írjuk meg helyette, hanem azt, hogy adjunk pár ötletet.
matematika.
Miből áll egy feladat?
Feladatterv, megoldás, ellenőrzés, diszkusszió. Utóbbi három sorrendjén lehet vitatkozni. De azon nem lehet, hogy a feladatterv a legnehezebb. És ehhez való tippadás is a feladatterv része fyi.
Jogos, elfogadom válasznak. :)
Azért van az oktató egy adott tárgyból.
+1
+1
Oktatótól kérdezni, vele konzultálni nem bűn.
Annó sok jó dolgot tanultam meg én is a tanórán kívül az oktatóimtól.
Szerintem ennek nem kellene kizárnia azt, hogy akár indítson egy fórumtémát, ahol összegyűlik pár ember, akiket érdekel a téma és megvitatja velük.
Felesleges úgy hozzáállni a dolgokhoz, hogy előnyszerzésre használja fel, kevesebb energiát fektet a feladatba, stb. Lehet így sokkal jobban elmélyül egy problémában, mint ha egyedül törné rajta a buksiját.
Ha érdekli, akkor úgy is foglalkozik vele eleget, ha meg nem, akkor tökmindegy, sosem lesz jó fejlesztő. Papir meg semmit sem jelent ezen a szinten, szerintem.
+1
+1
vagy akkor innentől ne lehessen a melóban felmerült problémákat se megvitatni a hupon, mert az csalás
problem solved
Míg egy házi az önálló problémamegoldás képességét próbálja megtanítani, hogy ne olyan ember kerüljön ki az egyetemről, aki minden karakterleütés előtt segítséget kér, mert teljesen bizonytalan mindenben, feltételezem/remélem, az iparban nem ilyen lesz.
Nem vitatom a házi feladatok hasznosságát, de nekem bőven volt már olyan tanárom, akitől nem lehetett segítséget kérni. Akkor pedig, hacsak nincs valaki a csoportban, aki nagyon ért a témához, marad az internet.
Az is lehet, hogy magánszorgalomból akar proramozást tanulni (mert a legtöbb suliban nem tanítanak), és ehhez régebbi versenyfeladatokat vesz elő. Nekem legalábbis Nemes Tihamér versenyfeladatnak tűnik, ott volt ez a fajta paraméterezés használva anno.
Nincs új a nap alatt, avagy a történelem ismétli önmagát.
LOL.
+1
Én igazából azt nem értem, hogy feladnak egy feladatot, amiben lényegében egy algoritmust kell lekódolni.
Mi a francnak beszélünk itt C#-ról, OO-ról, amikor az ilyen feladaton pont nem az OO skilljeit, hanem az algoritmuselméleti skilljeit fogja csiszolgatni. Innen is csókoltatom a tisztelt feladatkiírót.
A hupper kolléga írta mellé a C#/OOP kitételt. Amúgy +1.
--
-1
Az OO skillek és az algoritmuselméleti skillek nem diszjunktak. Nem mindegy, hogy OO elvek alapján hogyan tervezel meg pl. egy rekurzió, szekvenciális feldolgozás stb. során átadandó absztraktabb adatszerkezetet. Jelen esetben pl. nemcsak a maximális árbevétel, hanem a tényleges nyertes lista is meghatározásra kell kerüljön.
Egy szóval nem mondtam, hogy nem diszjunktak, de ez ALAPVETŐEN egy algoritmuselméleti probléma, és nem egy OO tervezési. Persze, bele lehet kalapálni az
összes OO tervezési mintát, csak éppen nem sok értelme van.
Nem az összes minta kell bele, csupán azok, amelyek alkalmazandók.
Az en otletem: rendezzuk az ajanlatokat a _parcellankenti_ legnagyobb ertekuvel kezdve, csokkeno sorrendben. Kezdjuk el osszeszedni oket az elejetol, amig tudunk ujat betenni a gyujtemenybe. Ha tobb egyforma erteku ajanlat van, ami valaszthato, akkor veletlenszeruen (mondjuk a parcella sorszama alapjan) valasszunk kozuluk, es ha a vegen a masik (nem valasztott) kimarad, akkor a gyujtest innen ujra megcsinaljuk, a masikat valasztva, es a vegen azt tartjuk meg, amelyik a nagyobb osszerteket adja.
Ez vajon megadja az optimalis valaszt minden esetben? Sejtesem szerint igen, es raadasul mar az elejen eleg jo megoldast ad (jobbat, mintha veletlenszeruen keresgelned a diszjunkt ajanlatokat).
A legrosszabb eset talan az, amikor sok egyforma erteku ajanlat van egymassal kis atfedesben (zippzar-szeruen). Azt, hogy ez O(micsoda), a kovetkezo hozzaszolora bizom :P
ui: csak hogy itt is meglegyen a link: http://nemes.inf.elte.hu/nemes_archivum.html
Ebben a megfogalmazásban ez két nyűgös feladat egyben.
1. Egyrészt:
google://weighted interval scheduling
Ezt az algoritmust kellene használnod. Az algoritmus lényege:
Ez utóbbi lépés úgy működik, hogy:
Jópofa, nem? :-)
2. Másrészt:
Objektumorientáltan ezt megcsinálni nem éri meg, célszerűbb integer tömbökkel operálni, gyorsabb is lesz meg talán egyszerűbb is. De ha a feladat objektumokat használni és fancy C#-osan akarod megoldani, akkor:
Akkor lenne köze, ha mittomén, az EddigAPályázatigBeszedhetőMaximálisPénz lenne a neve egy attribútumnak, de ez logikátlan, az objektum nem tudhatja, hogy ő egy rendezett listában ácsorog és nem tud a többi pályázatról - juteszembe, ha nagyon akarod, lehet erre a SortedList-ből örököltetni egy osztályt, ami ezt is nyilvántartja.
Egyébként egy kis érdekesség: az EzekkelAPályázatokkalHozomALegtöbbPénzt tipikusan "szép", objektumorientált megoldás, ami egyrészről szép és hasznos, másrészről viszont randa és memóriapazarló. Objektumok nélkül lehet jobban csinálni ezt a feladatot, az objektumorientált programozás nem ilyen feladatokhoz való.
Ha még fancybbet akarsz, akkor lehet LINQ-kel is csinálni, de ahhoz nem értek, majd valaki más leírja :-)
+1
Ez a leggyorsabb és legegyszerűbb algoritmus.
Annyi kiegészítést tennék az 1. részhez, hogy
- vagy kell még egy tömb, amiben gyűjtöd, hogy az adott pályázat begyűjtött pénzének kiszámolásához melyik megelőző pályázatot használtad fel. Ezek alapján lehet majd megmondani, hogy mely pályázatok lettek a nyertes pályázatok.
- vagy kell még egy kis algoritmus, ami visszafelé nézi, hogy az értékek alapján melyek a nyertes pályázatok.