Van egy probléma, amit régóta próbálok megoldani. Nem létkérdés, a régi ELITE számítógépes játékból ered, abból "absztraháltam".
Szóval: adott egy áru lista kellően sok elemmel. Minden áruról tudjuk a térfogatát és az értékét. Szeretnénk egy rakteret úgy feltölteni, hogy a lehető legnagyobb értékű áru kerüljön a raktérbe.
Kicsit konkretizálva: Adott egy 100 egység méretű raktér. Adott egy 100 elemű áru lista, kb ilyesmi:
Áru | Térfogat | Érték |
Áru 1 | 15 | 1414.3851 |
Áru 2 | 80 | 7613.9906 |
Áru 3 | 70 | 6981.7767 |
Áru 4 | 65 | 6772.0219 |
Áru 5 | 100 | 10339.2598 |
Áru 6 | 65 | 6498.7702 |
Tehát vannak áru típusok, amik egyedül is kitöltik az egész rakteret (pl Áru 5), de ha kisebb árut pakolok be, akkor több dolgot is be tudok rakni (pl Áru 1 + Áru 3).
Olvasgattam a témában, és találtam egy csomó cikket konténer feltöltés optimalizációra, de nekem azok túl bonyolultak, pl én nem szeretnék az egyes áruk alakjával foglalkozni, meg hogy miket lehet egymásra rakni, stb.
Két úttal próbálkoztam: Először arra gondoltam, hogy meghatározom, maximum hány áru fér be a listáról a raktérbe. Erre találtam egy gyors és egyszerű algoritmust. Az volt a tervem, hogy legenerálom ezzel a maximális mérettel az összes lehetséges al-listát, és kiválasztom a legnagyobb értékűt, de rájöttem, hogy 100 elemű kiindulási listával és pl 10-13 maximális áruszámmal a lehetséges listák száma túl nagy, nem végeznék valós időben.
Ezután nagyfiam javaslatára megpróbáltam egy rekurziós megoldást: legeneráltam az áruk fajlagos értékét (érték/térfogat), ez alapján sorba rendeztem az árukat. Vettem az első elemet (a legnagyobb fajlagos értékű árut), ami még befér a raktérbe, és beraktam a listába. Megnéztem, mennyi szabad raktér maradt, és ha az több, mint a legkisebb térfogatú áru, akkor a maradék raktér mérettel loopoltam a rekurziós függvényt. Szemléltetve: Lett egy új oszlop a táblázatomban fajlagos érték néven: érték/térfogat. TFH a legnagyobb fajlagos értékű áru térfogata 70, ezt berakom a listámba. Maradt 30 méretű raktér, az eredeti árulistámon 5 a legkisebb méretű áru, tehát loop. Kidobok mindent , ami nagyobb mint 30 (hiszen úgyse férnének már be), és megint veszem a legnagyobb fajlagos méretű árut, és hozzáadom a listához. Mondjuk a térfogata 25, tehát maradt még ö méretű rakterem, tehát loop.
Ezzel a megoldással az a bajom, hogy nem látom be, hogy valóban a legjobb értékű árulistát generálja nekem. Cserébe elég gyorsan végez, és legalább valamilyen listát generál.
Tudnátok adni fogozókat, hogy jó irányban indultam e el, esetleg hogyan lehetne ellenőrizni, hogy a rekurziós megoldás mennyire jó, vagy van e értelmes alternatíva? Érdekelne heurisztikus megoldás is, de ott megint elakadtam olyanokon, hogy generáljak pl max 3 elemű allistákat, aminek az össztérfogata 100. (Ha tudnék ilyet, akkor esetleg meg tudnám saccolni az értékösszeg eloszlását, hogy lássam, mennyire jó a rekurziós megoldásból kapott lista.)
Bármi kommentet megköszönök.
- 357 megtekintés
Hozzászólások
Ez nem a lineáris programozás lesz?
- A hozzászóláshoz be kell jelentkezni
cat "Hátizsák probléma" | sed 's/súly/térfogat/' :)
BlackY
"Gyakran hasznos ugyanis, ha számlálni tudjuk, hányszor futott le már egy végtelenciklus." (haroldking)
- A hozzászóláshoz be kell jelentkezni
Nekem ez tiszta hátizsákpakolásnak tűnik, az meg emlékeim szerint NP-teljes. Ha nem kézzel akarod megoldani, akkor nekifutnék valami contraint solverrel, azok erre vannak kitalálva.
- A hozzászóláshoz be kell jelentkezni
- A hozzászóláshoz be kell jelentkezni
Nincs mit.
Off: nem túl hosszú R-használattal a hátam mögött úgy vettem észre, hogy elég sok mindenre van kb. kész megoldás.
- A hozzászóláshoz be kell jelentkezni
- A hozzászóláshoz be kell jelentkezni
A legegyszerűbb, ha fogod, es brute force-al megprobálod az összes lehetőséget beletömni a raktérbe, és a végén kiválasztod a legjobbat.
Ez úgy nagyon nem éri meg, de ha optimalizálsz ezen backtrackkel levágva az ertelmetlen ágakat (ahol már sehogy sem lehet annyi értékű árut belerakni, mint az eddigi legjobb megoldás), akkor jó lesz.
Egyszerű, és látod, hogy mit csinál :)
“Any book worth banning is a book worth reading.”
- A hozzászóláshoz be kell jelentkezni
P = NP esetén jó lehet, de kissé sokáig tud futni az ilyen ... :)
- A hozzászóláshoz be kell jelentkezni
Köszönöm mindenkinek, hogy a Knapsack problem felé irányítottatok, ez alapján már tovább tudok haladni.
Csaba
- A hozzászóláshoz be kell jelentkezni
Mivel már megoldottátok, érdemes továbbfejleszteni a jómunkás mentalitás nevő optimalicációs algoritmust használva.
Az én ötletem az, hogy végigmész lineárisan a listán, és elkezded bepakolni az árut a raktárba.
Ami befér bemegy, ami nem fér be, az leteszed a raktár mellé, és jöhet a következő elem.
Amikor végigérsz a listán, letakarod egy fóliával a kint maradt árut, hogy ne verje el az eső, és hazamész inni egy sört.
Ez szerintem gyorsabb mint matekolni, és sört is ihatsz, szóval megint nyert a józan paraszti ész, és a lustaság.
:-P
- A hozzászóláshoz be kell jelentkezni