Licit algoritmus - C# OOP

Programozás - kezdő

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.

  • 4211 megtekintés

( dotnetlinux | 2015. 12. 01., k – 00:00 )

Szerintem prog.hu-ra való téma, ez a HUnixP. De majd @tray kijavít.

( joco01 v | 2015. 12. 01., k – 00:09 )

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.

--

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.

--

( dotnetlinux | 2015. 12. 01., k – 00:10 )

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.

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: 


ha(turinggép(G).leáll(input:=I,szimuláltlépéskorlát:=Infinity)){
    blokk();
}

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

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.

<@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!

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)

Mivel megvan határozva a bemenő adat max mennyisége, ...

Hol? BTW. alaphalmaz hatványhalmazának fogalma megvan? És annak az elemszáma is megvan?

Nálam helyből 1-es, ha valaki egy faék egyszerűségű programot teljesen feleslegesen túlbonyolít.

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)

... egy kevés cpu idő beáldozásával.

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ő.

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.

( uid_19334 | 2015. 12. 01., k – 00:22 )

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)

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

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.

( Szenti v | 2015. 12. 01., k – 12:36 )

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.

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.

( digger86 | 2015. 12. 01., k – 13:48 )

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

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.

Mennyire sportszerű házi feladatot hupperekkel megoldatni?

Semennyire, ebben egyetértünk.

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!

Hogy mit is jelentsünk, hova? Szerintem a posztoló nem azt kérte, hogy írjuk meg helyette, hanem azt, hogy adjunk pár ötletet.

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.

( sz332 v | 2015. 12. 01., k – 18:43 )

É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.

-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.

( haspokember | 2016. 01. 02., szo – 20:22 )

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

( uid_4656 v | 2016. 01. 03., v – 01:26 )

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: 


- a pályázatokat az utolsó megvásárolni szándékozott parcella sorszáma szerinti növekvő sorrendbe kell rendezni
- kell csinálni egy segédtömböt, ami azt tartalmazza, hogy az egyes pályázatok esetében melyik az a rendezett sorban őt megelőző utolsó pályázat, amellyel nincs átfedése
- majd csinálni kell egy tömböt amelyben összegyűjtöd, hogy az elsőtől az adott pályázatig válogatva a pályázatok közül mennyi a maximálisan begyűjthető pénz.

Ez utóbbi lépés úgy működik, hogy: 


- kiindulsz abból, hogy 0 pénzt gyűjtesz be, 0 pályázatot válogatsz be
- hozzácsapod az első pályázatot, így az első pályázatig X pénzt gyűjtesz be
- megnézed a következő pályázatot, és:
    - kikeresed a segédtömbben, hogy mely másik utolsó pályázattal nincs átfedésben
    - kiszámolod, hogy mennyi lenne a begyűjtött pénz, ha ezzel az átfedésben nem lévő pályázatokból beszedhető maximális pénzhez hozzáadod az ebből a pályázatból beszedhető pénzt
    - megnézed, hogy mennyi lenne az a pénz, amennyit enélkül a pályázat nélkül, legfeljebb az előző pályázat felhasználásával begyűjthetnél
    - (ezt mindkettőt ki lehet számolni ennek a tömbnek a korábban kiszámolt elemeiből és a segédtömbből)
    - a kettő közül a nagyobbat beírod a tömbbe
- a végén kijön a maximálisan összeszedhető pénz.

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: 


- csinálhatsz egy Pályázat osztályt, amelynek lehet ElsőParcellaIndex, UtolsóParcellaIndex és Pénz property-je
- ebből örököltethetsz egy KiegészítőInformációsPályázat osztályt, amelynek:
    - van egy EzAzUtolsóAmivelNincsÁtfedésben attribútuma is
    - implementálja az IComparer<Pályázat> interface-t úgy, hogy a komparátor a saját UtolsóParcellaIndex-et hasonlítja a (másik) Pályázat UtolsóParcellaIndex-éhez
    - van egy EzekkelAPályázatokkalHozomALegtöbbPénzt HashSet<Pályázat>-a
- az inputfájl beolvasásakor rakhatod rögtön egy SortedList-be a dolgokat, a komparátort használva
- kétszer iterálsz a SortedList-en a fentebbi algoritmus szerint
    - az első körben kitöltöd a EzAzUtolsóAmivelNincsÁtfedésben attribútumokat
    - a második körben meg töltögeted mindenhol a HashSet-eket az előző eredményekből és magukból az objektumokból
- én a végső beszedhető pénzt külön változóban/struktúrában/objektumban tárolnám, mert logikailag nincs köze ezekhez az objektumokhoz

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. 


- ha az utolsó pályázat értéke megegyezik az előzőével, akkor ez nem nyertes, nézem az előzőt
- ha nem egyezik meg, akkor ez nyertes pályázat és az előtte, vele nem átfedésben levővel folytatom a vizsgálatot