N számú ember N számú dolgának cserélgetése úgy, hogy a legtöbb csere jöhessen létre.
Sziasztok!
Van egy projektem. Gyakorlatilag a lényegi megvalósítás legelején elakadtam. :(
A feladat: vannak a usereink (N számú) nekik vannak cuccaik (N számú) és minden cucchoz tartozik minimum 1 cserecucc (N számú lehet) amire hajlandók cserélni.
Pl: Van Pisti neki van 1 almája amit körtére cserélne P C=alma CSC=Körte, Gézának van körtéje de, cseresznyére cserélné, G C=Körte CSC= cseresznye és van Lali akinek van cseresznyéje de, almát szeretne érte vagy körtét. L C=cseresznye CSC= alma || körte.
Itt ugye Lali cserélhetne Gézával, Lalinak lesz körtéje Gézának cserkója frankó de, mi van Pistivel?
Pisti cseréljen Gézával körtét almára majd az almát cserkóra Lacival. mindenki örül.
Ez így egyszerű de nagy számokkal, hogyan? Bocsánat ha nem elég érthető.
phpval szeretnék dolgozni ha van megoldás.
Köszönöm a figyelmeteket!
WZS
■ Van egy projektem. Gyakorlatilag a lényegi megvalósítás legelején elakadtam. :(
A feladat: vannak a usereink (N számú) nekik vannak cuccaik (N számú) és minden cucchoz tartozik minimum 1 cserecucc (N számú lehet) amire hajlandók cserélni.
Pl: Van Pisti neki van 1 almája amit körtére cserélne P C=alma CSC=Körte, Gézának van körtéje de, cseresznyére cserélné, G C=Körte CSC= cseresznye és van Lali akinek van cseresznyéje de, almát szeretne érte vagy körtét. L C=cseresznye CSC= alma || körte.
Itt ugye Lali cserélhetne Gézával, Lalinak lesz körtéje Gézának cserkója frankó de, mi van Pistivel?
Pisti cseréljen Gézával körtét almára majd az almát cserkóra Lacival. mindenki örül.
Ez így egyszerű de nagy számokkal, hogyan? Bocsánat ha nem elég érthető.
phpval szeretnék dolgozni ha van megoldás.
Köszönöm a figyelmeteket!
WZS
Első ránézésre ez egy
Én erősen kétlem, hogy ez
P -[alma]-> L -[cseresznye]-> G -[körte]-> P
Ha így nézzük, akkor ja,
Grafélmélet
.
| P | | L | | G |
| | <-[k]- | | <-[k]- | |
Magát a problémát szerintem úgy a legegyszerűbb megoldani, hogy megnézed az igényeket és a felajánlásokat, és eltérő előjellel összeadod őket. Először csak az olyanokat, amiknél 1:1 termék van, a maradékon a többiek osztozhatnak. Ebből nagyjából kijön, hogy mi az, ami ténylegesen megoldható.
pl:
G: +k-cs
L: +cs-(a|k)
->
+a-(a|k)
->
.
A tranzakcióknál azt érdemes fejben tartanod, hogy több dolog van, amik ellent mondhatnak egymásnak:
- a legtöbb feltétel teljesüljön (P, G és L is elégedett legyen)
- egy emberen a lehető legkevesebb tranzakció fusson át (L-nak ne kelljen 2 tranzakciót is végrehajtani), különösen, ha a végén nem kapja meg azt, amit akart
- a legkevesebb tranzakciót használd fel (3 emberre 2 tranzakció lenne a legkevesebb, de a probléma csak 3 tranzakcióval volt megoldható)
Ezeknek gondolom vannak korlátaik, pl senki nem fog napi ezer tranzakciót végrehajtani, ha árumozgatás is van, stb...
Nem hiszem, hogy találsz kész általános megoldást a problémára, ezekből próbálj elindulni, aztán fejleszteni egy sajátot.