A ládapakolási probléma egy NP-nehéz kombinatorikus optimalizációs probléma. A cél az, hogy egy adott tárgyhalmazt úgy helyezzük el fix méretű ládákba (konténerekbe), hogy a felhasznált ládák száma minimális legyen.
Az alábbi implementáció a First Fit algoritmust mutatja be, amely egyszerű, de hatékony megoldást kínál a ládapakolási problémára.
def first_fit(items, bin_capacity=1.0):
"""
First Fit algoritmus a ládapakolási problémára.
:param items: A tárgyak listája (méretekkel).
:param bin_capacity: A ládák kapacitása (alapértelmezett: 1.0).
:return: A ládák tartalma.
"""
bins = # Lista a ládákról, amelyek tartalmazzák a tárgyakat
for item in items:
placed = False
# Próbáljuk elhelyezni a tárgyat a már nyitott ládák egyikébe
for b in bins:
if sum(b) + item <= bin_capacity:
b.append(item)
placed = True
break
# Ha nem találtunk helyet, nyitunk egy új ládát
if not placed:
bins.append()
return bins
# Példa használat
items =
print("Tárgyak mérete:", items)
# Ládapakolás futtatása
result = first_fit(items)
# Eredmény kiírása
print("\nLádák tartalma:")
for i, b in enumerate(result):
print(f"Láda {i + 1}: {b}")
print(f"\nFelhasznált ládák száma: {len(result)}")
Példa bemeneti adatokkal:
Tárgyak mérete: Ládák tartalma: Láda 1: Láda 2: Láda 3: Láda 4: Láda 5: Felhasznált ládák száma: 5
def first_fit_decreasing(items, bin_capacity=1.0):
"""First Fit Decreasing algoritmus."""
items_sorted = sorted(items, reverse=True)
return first_fit(items_sorted, bin_capacity)
# Példa használat
result_ffd = first_fit_decreasing(items)
print("\nFFD algoritmus - Ládák tartalma:")
for i, b in enumerate(result_ffd):
print(f"Láda {i + 1}: {b}")
print(f"\nFelhasznált ládák száma (FFD): {len(result_ffd)}")
FFD algoritmus - Ládák tartalma: Láda 1: Láda 2: Láda 3: Láda 4: Felhasznált ládák száma (FFD): 4
Az FFD algoritmus gyakorlati esetekben jól használható, mivel gyors és jó közelítő megoldást ad.