Raktér feltöltés optimalizációja

Fórumok

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.

Hozzászólások

Ez nem a lineáris programozás lesz?

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)

Szerkesztve: 2021. 04. 12., h – 12:48

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 :)

“Politikusok a döntésüket a háttérben dolgozó szakemberek javaslatai alapján hozzák meg." (Trey)

Köszönöm mindenkinek, hogy a Knapsack problem felé irányítottatok, ez alapján már tovább tudok haladni.

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