[Help] C++ feladat, nem tudom megoldani

Fórumok

sziasztok, elég fontos lenne ha ezt a feladatot meg tudná oldani valaki.

Nevesincs város polgármestere elhatározta, hogy értékesíti a város mellett levő téglalap alakú földdarabot. A földet egyforma méretű parcellákra osztotta.

A polgármester úgy döntött, hogy a parcellákat nyilvános pályázat keretében adja el, azaz egy adott határidőig minden érdeklődő lezárt borítékban leadhatja ajánlatát. Egy pályázó csak egy ajánlatot nyújthat be, amelyben meg kell adnia, hogy melyik parcellá-tól melyik parcelláig terjedő részt kívánja megvenni, és mennyiért.
A pályázat sikeres volt, a határidő lejártáig N pályázat érkezett. Ezek közül ki kell választani azokat az ajánlatokat, amelyek a legtöbb bevételt eredményezik, s persze úgy, hogy egyetlen parcellát sem ítélnek oda egynél több pályázónak. Egy-egy pályázó vagy az összes kért parcellát megkapja, vagy egyet sem kap meg. Előfordulhat, hogy a maxi-mális bevétel eléréséhez nem kell eladni az összes parcellát.
Írj programot licit.cbp (main.cpp), amely megadja a választ a polgármes-ter problémájára!
Bemenet:
A licit.be állomány első sorában a pályázatok N száma (1<=N<=100) és a parcel-lák M száma (1<=M<=100) található, egy szóközzel elválasztva. A következő N sor az egyes pályázók adatait tartalmazza, a pályázókat ez a sorrend azonosítja. Mindegyik sorban 3 szám van egy-egy szóközzel elválasztva: A B FT, ami azt jelenti, hogy a pályá-zó az A sorszámú parcellától (1<=A<=M) a B sorszámú parcelláig (A<=B<=M) terjedő ré-szért FT forintot fizetne (1000<=FT<= 1000000).
Kimenet:
A licit.ki állomány első sorába az elérhető legnagyobb bevételt kell írni. A má-sodik sorba a nyertes pályázók sorszámai kerüljenek egy-egy szóközzel elválasztva. Ha több megoldás is van, csak egyet kell kiírni (bármelyiket).

Példa:
licit.be
4 5
1 5 10000
2 4 5000
4 5 5000
4 4 6000

licit.ki
11000
2 4

Hozzászólások

Ha már nem az a kérés, hogy segítsenek neked megoldani, hanem hogy valaki oldja meg helyetted, visszakérdezek:
Mennyit fizetsz érte?

Nem jó a példád, mert a 2-es és 4-es pályázat is megvenné a 4-es parcellát.

Szokásos reakció ilyen kérésekre: Mutasd a kódot, meddig jutottál.
(No meg: ez nem házifeladat megoldó portál)

Ez egy milyen jó kis feladat. Ráadásul C-ben lehet megoldani. Anno nekem ilyet Piszkálban meg Bézikben kellett írni. Takarítottam is keményen a billentyűzetet az okádéktól lol.

Ja igen, és virítsd a kódot hadd nézzük meddig jutottál.

--
GPLv3-as hozzászólás.

A kérdés: bármilyen megoldás jó, vagy emberi idő alatt le is futó megoldást várnak?

Mert a "buta" megoldást aki nem tudja összeütni, az inkább ne foglalkozzon informatikával...

szerintem csak motiválatlan egy kicsit. amikor az ember sokáig csak warningok meg errorok formájában kap visszajelzést, akkor hajlamos időnként elkedvetlenedni.

viszont ha most elkezdek szentbeszédet tartani arról, hogy mekkora szívás 25 évesen egyetemre jelentkezni akarni, akkor mindenki ásítva fogja elcsukni a böngészőablakot.

Hát azért ezzel vitatkoznék. Az egyetemen nem azt fogják megtanítani (illetve azért van róla szó), hogy paszkálban vagy cében (vagy bármilyen nyelven) hogyan kell egy problémára programot írni. Hanem az elméleti alapokat tanulhatod meg ha képes vagy rá. A mély elméleti (erős matematika) alapok nélkül nem sokat ér az a tudás ha "csináltál már programot". Én úgy gondolom, hogy jellemzően általános iskolában és középsuliban egyszerűbb elméleti alapokkal és kicsit töb gyakorlati megvalósítással tanítják a programozást. De ez nem igazi programozás. Ellenben a felsőoktatásban elsajátíthatsz egy csomó olyan mélyebb matematikai tudást (analízis, logika, formális nyelvek automaták, algoritmusok, programozási paradigmák, stb) minek segítségével megoldhatsz bonyolult feladatokat. Tehát nem egy vagy több programnyelv ismerete tesz (jó) programozóvá hanem az, hogy az elmélet birtokában bármilyen programnyelven képes vagy megoldó programot írni. Én úgy gondolom, hogy ezt a tudást nagyjából a felsőoktatás tudja megadni a középiskola pedig nem.

--
maszili

Ha már hasonlatoknál tartunk: elméleti tudás nélkül programozni tanulni meg olyan, mint fórumokból nyelvet tanulni.

Teljesen nyilvánvaló (legalábbis számomra), hogy az elméleti és a gyakorlati tudás kiegészíti egymást, az egyetem csak az elméleti tudás megadására alkalmas, abban is csak részben. Ahhoz a hallgatónak is tennie kell valamit, hogy a megfelelő szintű elméleti tudást megszerezze (önképzés, választható tárgyak, stb.), a gyakorlatiról már nem is beszélve.

--
Don't be an Ubuntard!

Szerintem rossz a hasonlatod.
Mint a topiknyitó példáján is látszik előbb egy elméleti megoldást kellene készítenie amit aztán a programnyelv segítségével visz át a gyakorlatba. Ha lövése sincs az elméleti alapokról akkor pl. hiába tudja nagyon ügyesen (mert azt már sokszor csinálta), hogyan kell c++ nyelven egy fájlt megnyitni...

--
maszili

Nos részben egyetértek veled, az egyetem elméleti oktatásban jó, és kell is az az elméleti oktatás, vagy legalábbis a nagy része. Azonban az, hogy volt kb. 6 java tantárgyam a Bsc. során, és 6-ból 5 (!) alkalommal elkezdtük az alapjaitól tanulni a Javát (szó szerint értsd, tehát "na és akkor gyerekek mi az hogy osztály? " stb.) az szerintem egy elég siralmas dolog.
Ennél már csak az a szánalmasabb, hogy volt akinek erre szüksége volt, mert gőze nem volt 5. alkalommal se a kivételkezelésről például.

Ja és itt az ELTE-ről beszélek, ami igaz, hogy köztudott hogy elméleti oktatásban a jobb, na de azért mégis...

Ez a sok java tárgy mind kötelező volt, választhatóba ezek után egyet se vettem fel.
Inkább a tanárok kiválsztásánál nem volt sokszor szerencsém, mert hozzátenném, hogy azért van 1-2 tanár aki normálisan tartja az órákat.
Csak vagy nehéz bekerülni hozzájuk, vagy nem ismerem egyiket se és akkor találomra kell választani.

nem csak ezt írtam, de te nyilván térdelőrajtban vártad, hogy valamibe beleköthess.

sőt ha tovább elemzem a dolgot, téged már a hozzászólásod megírásának elkezdése pillanatában előre zavart az a gondolat, hogy nem fogom szó nélkül hagyni. pedig azt kellett volna tennem...

de ahhoz túl sok a szabadidőm.

Pedig igaza van, Erendis nem sok segítséget adott a kérdezőnek, ellenben különböző offtopic hozzászólásokat generál. Az még hagyján, amikor althreadbe reagál, de ezen thread nyitó commentjének semmi értelme nem volt. Még csak nem is troll, ami legalább a topicot olvasókat szórakoztatná.

--
Don't be an Ubuntard!

"nem tudom megoldani "

Egy jó hírem van, de kettő lesz belőle.

Ha sokáig gondolkozol rajta, utánajársz és próbálkozol, mégis meg fogod tudni oldani.
Illetve ha mégsem tudod, akkor sincs baj, mert még nem késtél el azzal, hogy pályát változtass.

ez ilyen biro által kiértékelt SZTE Algoritmusok és adatszerkezetek kötelező feladat szagú... pfejj... :) azért napközben elgondolkodunk rajta kollégámmal, ha másért nem, a nosztalgia kedvéért :D

--
A gyors gondolat többet ér, mint a gyors mozdulat.

Addig eljutottal, hogy irj egy main.cpp-t? Ha igen, mi van benne?
--

Ki oda vagyik, hol szall a galamb, elszalasztja a kincset itt alant. | Gentoo Portal 

Javaslat: szakadj el a nyelvtől, előbb az algoritmust állítsd össze! Utána kezdd el "lefordítani" C vagy C++ vagy akármilyen konkrét nyelvre.

(Mindenesetre ha és amennyiben a példa tényleg így szerepel a feladat kiírásában, akkor az oktatás ill. a tanerő hozza a formáját.)

Pontatlan feladatspecifikáció.
Mennyit kér a polgármester?

A leírás alapján ez nekem KÖMAL feladatnak tűnik. Nézz szét első körben a pontverseny archívumában, hátha fent van a megoldás.

Hogy valami konstruktívat is olvass:
Először ismerkedj meg a backtrack algoritmussal.

Amire szükséged lesz:
Egy aktuális lista, ami tárolja az elfogadott ajánlatokat, egy megszorítással: a listába csak olyan ajánlatokat adunk hozzá, amik nagyobb sorszámúak, mint a legutolsó ajánlat (ha van)
Egy eddigi legjobb lista (az előző lista elmentve, mint legjobb ajánlat)
Egy eddigi legjobb összérték (az előző listához tartozó összeg)

Én valahogy úgy kezdenék neki, elkezdeném az (*)aktuális listához hozzáadni a hozzáadható (megszorítás) ajánlatokat.
Ezt addig csinálom, amíg tudom bővíteni a listát.
Ha már nem, akkor ha az aktuális lista összértéke nagyobb, mint a fejlegyzett legjobb összérték, elmentem az aktuális listát, mint legjobb lista, és az aktuális összértéket, mint legjobb összérték.

Ezután eltávolítom az aktuális listából a legutolsó elemet, és visszatérek (*)-hoz

Ha nem tévedek, akkor az algoritmus úgy áll le, hogy üres az aktuális lista, az elmentett listában lesz az optimális ajánlat, az ára pedig a legjobb összértékben.

Megjegyzések:
-Lehet, hogy tévedek :-)
-Ha bárhol ezt a postot továbbközlöd, hogy megvan az algoritmus és hogyan implementáld, megharaplak!

Látom nem mutatsz nagy érdeklődést a válaszok iránt, de azért felteszek egy kérdést, ami eddig nem volt.

Ha ez egy házi feladat, valamilyen programozást oktató tárgyból, vagy valamilyen algoritmuselméletet oktató tárgyból adták ki?

Előbbi esetében a megvalósítás szempontjából a használt algoritmus gyakorlatilag lényegtelen, egy exponenciális lefutású megoldás is teljesen megfelel, a lényeg a beolvasás és a megfelelő osztályhierarchia kialakításán van, persze a specifikációnak megfelelő kimenet előállításán kívül.

Utóbbi esetben pedig sokkal inkább számít az algoritmus, engem a hátizsák problémára emlékeztet, persze annak egy kötöttebb verziója (amit ki lehet használni az algoritmus megalkotásakor). Ez esetben nem érdemes sokat foglalkozni azzal, hogy maga a program mennyire elegáns, elég, ha a specifikált bemenetre a specifikációnak megfelelő kimenetet tudod garantálni, gyakorlatilag bármilyen módon, amit a C++ megenged.

Mindezt csak azért írom, mert a feladat sürgős, ha nem lenne az, akkor mindkét szempontnak megfelelő program az ideális megoldás.

--
Don't be an Ubuntard!

[off]
Az ilyen feladatoknál mindig hiányolom az i/o mennyiséget.
Mellékelhetnének a kitűzők 1-2Megányit ami "minden" lehetséges
konfigurációt tartalmaz. Ezek itt pl. nem szégyellik kitenni a nagy tesztállományaikat:
http://plg1.cs.uwaterloo.ca/~acm00/
Ez azért se rossz dolog mert így hamarabb kiderül ha a kitűző se gondolt mindenre... Van ilyen is.
Szegény "mukso" még ha meg is oldaná valamilyen módon, nem lehetne (empirikusan) biztos a helyességben,
hacsak nem bizonyítaná be (de akkor meg nem tette volna fel itt a kérdést).
[/off]
A megoldás keresésnél a következő utat választanám:
O(2^n) -> O(n^2) -> O(nlog(n)) :)

Tök jópofa feladat, megcsináltam (bár nem C++-ban, hanem Javaban, de igazából édesmindegy). O(n*log(n))-es megoldást tudok rá adni.

Abból indulj ki, hogy:
- ha felteszed egy tetszőleges elemről, hogy benne van a végeredményben, akkor már csak két "kisebb" problémát kell megoldanod, az elemtől jobbra és az elemtől balra lévő további elemekre külön-külön
- esélyes, hogy ha tárolod a kisebb problémák megoldásait, akkor azok eredményét többször is fel tudod használni.

Sok sikert! :-)

kicsit off, de

Donald E. Knuth A számítógép programozás művészete I.-IV.

OpenBSD 5.0/i386 theo for the prezident:D