Határidő: 2022-04-23 24:00

• A ládapakolás feladatban a bemeneten megadott \((s_i)_{i = 1}^n\), \((0 < s_i \le 1)\) súlyokról kell meghatározzuk, hogy minimálisan hány \(1\) kapacitású ládába férnek el. A probléma NP-teljes, így hatékony megoldás (jelenlegi ismereteink szerint) nem áll rendelkezésre, ám számos közelítő algoritmus született rá. Ebben a feladatban néhány közelítő heurisztika vizsgálata lesz a cél.
• A ladak.py fájlban megadtunk egy olyan keretprogramot, ami egy fix bemeneten vizsgál egy alsó korlátot és három közelítő algoritmust a ládapakolás problémára:
  1. Az OPT értéke a tárgyak összsúlyának felső egészrésze, azaz \[\left\lceil\sum_{i=1}^n s_i\right\rceil,\] ami egy alsó korlát a szükséges ládák számára.
  2. Az FF (first fit) algoritmus a tárgyakat a megadott sorrendjükben próbálja elhelyezni a ládákba úgy, hogy a soron következő tárgy mindig a legelső olyan ládába kerüljön, ahova még befér. Ha egyetlen ládaba sem fér el, akkor új ládát nyit neki.
  3. Az FFD (first fit decreasing) algoritmus hasonló az FF-hez, ám előbb csökkenő sorrendbe rendezi a tárgyakat.
  4. A BF (best fit) heurisztika minden tárgyat abba a ládába helyez el, ahol a legkevesebb szabad hely marad. Ha egyetlen ládaba sem fér el, akkor új ládát nyit.
• Módosítsuk a ladak.py fájlt megírva a hiányzó algoritmusokat!
  1. Valósítsuk meg a first_fit függvényben az FF algoritmust.
  2. Valósítsuk meg a first_fit_d függvényben az FFD algoritmust. Ügyeljünk arra, hogy a Python a listákat referencia szerint adja át, így ha a súlyokat tartalmazó listát rendezzük, az a hívó által átadott listát közvetlenül módosítja. Ehelyett inkább dolgozzunk a lista egy másolatával!
  3. Tanulmányozzuk a BF algoritmust megvalósító és már megírt best_fit függvény kódját.
  4. A fix targyak lista helyett állítsunk elő 1000 elemű, 0 és 1 közötti véletlen súlyokat tartalmazó listát, és hívjuk meg ezzel a pakoló függvényeket.
  5. Futtassuk le néhányszor a programot! Mit tapasztalunk, hogy működnek a közelítő algoritmusok a generált véletlen bemeneteken? Tapasztalatunkat tömören írjuk be a kódba megjegyzésként.