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

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:

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.