Kedves Diákjaim! elérkeztünk a mindenki rémálmához, ez a komplex algoritmus, érettségi szint feletti feladat, ez sokaknál kiveri a biztosítékot, de ne feledjétek a programozás attól szép hogy nehéz. Egy logisztikai központ szállítmányozási és rakomány-optimalizálási problémáját modellezi implementálja ez a feldat. A program két részből áll: egy mohó (greedy) algoritmusból a legértékesebb rakomány kiválasztásához, és egy rekurzív mélységi keresésből (DFS) a logisztikai útvonalak feltérképezéséhez.
-----------------
from typing import List, Dict, Tuple
# ==========================================
# 1. RÉSZ: MOHÓ ALGORITMUS (Rakomány optimalizálás)
# ==========================================
def csomag_pakolas_optimalizalas(csomagok: List[Dict], teherbiras: float) -> Tuple[float, List[Dict]]:
"""
Kiválasztja a legértékesebb csomagokat a teherbírási limitig.
A mohó stratégia: Mindig a legnagyobb fajlagos értékű (érték / súly) csomagot választjuk.
"""
# Fajlagos érték kiszámítása és csomagok rendezése csökkenő sorrendben
# Képlet: fajlagos_ertek = ertek / suly
csomagok_rendezett = sorted(
csomagok,
key=lambda x: x['ertek'] / x['suly'],
reverse=True
)
aktualis_suly = 0.0
ossz_ertek = 0.0
szallitmany = []
for csomag in csomagok_rendezett:
if aktualis_suly + csomag['suly'] <= teherbiras:
aktualis_suly += csomag['suly']
ossz_ertek += csomag['ertek']
szallitmany.append(csomag)
return ossz_ertek, szallitmany
# ==========================================
# 2. RÉSZ: GRÁFBEJÁRÁS (Rekurzív mélységi keresés - DFS)
# ==========================================
def logisztikai_utvonal_kereses(graf: Dict[str, List[str]], aktualis_allomas: str, cel_allomas: str, meglatogatott: set = None) -> bool:
"""
Rekurzív mélységi keresés (DFS) annak ellenőrzésére, hogy van-e útvonal
két logisztikai csomópont (pl. raktár és célállomás) között.
"""
if meglatogatott is None:
meglatogatott = set()
if aktualis_allomas == cel_allomas:
return True
meglatogatott.add(aktualis_allomas)
if aktualis_allomas in graf:
for szomszed in graf[aktualis_allomas]:
if szomszed not in meglatogatott:
# Rekurzív hívás a szomszédra
if logisztikai_utvonal_kereses(graf, szomszed, cel_allomas, meglatogatott):
return True
return False
# ==========================================
# TESZT ADATOK ÉS FUTTATÁS
# ==========================================
if __name__ == "__main__":
# --- 1. Teszt: Mohó algoritmus ---
raktar_keszlet = [
{"id": "CS-1", "suly": 15.0, "ertek": 3000.0},
{"id": "CS-2", "suly": 40.0, "ertek": 7000.0},
{"id": "CS-3", "suly": 10.0, "ertek": 2500.0},
{"id": "CS-4", "suly": 30.0, "ertek": 4500.0},
{"id": "CS-5", "suly": 25.0, "ertek": 6000.0}
]
max_teherbiras = 80.0
optimalis_ertek, pakolt_csomagok = csomag_pakolas_optimalizalas(raktar_keszlet, max_teherbiras)
print("--- 1. MOHÓ ALGORITMUS EREDMÉNYE ---")
print(f"Maximális teherbírás: {max_teherbiras} kg")
print(f"Elért összérték: {optimalis_ertek} Ft")
print("Bepakolt csomagok részletezése:")
for cs in pakolt_csomagok:
print(f" - {cs['id']}: Súly: {cs['suly']} kg, Érték: {cs['ertek']} Ft")
# --- 2. Teszt: Gráfbejárás (DFS) ---
# Logisztikai kapcsolatok (irányított gráf)
logisztikai_halozat = {
"Budapest": ["Debrecen", "Miskolc"],
"Debrecen": ["Nyíregyháza", "Szolnok"],
"Miskolc": ["Nyíregyháza"],
"Szolnok": ["Szeged"],
"Nyíregyháza": [],
"Szeged": []
}
indulas = "Budapest"
cel = "Nyíregyháza"
van_ut = logisztikai_utvonal_kereses(logisztikai_halozat, indulas, cel)
print("\n--- 2. REKURZÍV GRÁFBEJÁRÁS (DFS) EREDMÉNYE ---")
print(f"Van közvetett vagy közvetlen logisztikai kapcsolat {indulas} és {cel} között? {'IGEN' if van_ut else 'NEM'}")
------------------
--- 1. MOHÓ ALGORITMUS EREDMÉNYE ---
Maximális teherbírás: 80.0 kg
Elért összérték: 16000.0 Ft
Bepakolt csomagok részletezése:
- CS-3: Súly: 10.0 kg, Érték: 2500.0 Ft
- CS-5: Súly: 25.0 kg, Érték: 6000.0 Ft
- CS-1: Súly: 15.0 kg, Érték: 3000.0 Ft
- CS-4: Súly: 30.0 kg, Érték: 4500.0 Ft
--- 2. REKURZÍV GRÁFBEJÁRÁS (DFS) EREDMÉNYE ---
Van közvetett vagy közvetlen logisztikai kapcsolat Budapest és Nyíregyháza között? IGEN
--------------
Futtatás; https://onecompiler.com/python#draft-tdxd
Nincsenek megjegyzések:
Megjegyzés küldése