Tartalomjegyzék:
Meghatározás - Mit jelent a hátizsák probléma?
A hátizsák probléma egy optimalizálási probléma, amely a probléma és a megoldás szemléltetésére szolgál. A nevét egy olyan forgatókönyvből származtatja, amely korlátozza a rögzített méretű hátizsákba behelyezhető cikkek számát. Adott súlyokkal és értékekkel rendelkező darabszám alapján a cél az, hogy a hátizsák súlyának korlátozása miatt a lehető legtöbb értéket érjék el a hátizsákban.
A Techopedia magyarázza a hátizsák-problémát
A hátizsák probléma egy kombinált optimalizálási probléma példája, a matematika és a számítástechnika témája az optimális objektum megtalálásáról az objektumkészlet között. Ez egy olyan probléma, amelyet több mint egy évszázadon keresztül vizsgáltak, és ez a kombinatorikus optimalizálás általánosan használt példaprobléma, ahol szükség van optimális tárgyra vagy véges megoldásra, ahol nem lehetséges a kimerítő keresés. A problémát olyan valós forgatókönyvekben lehet megtalálni, mint például az erőforrások elosztása pénzügyi korlátokban, vagy akár a befektetések és a portfóliók kiválasztásakor. Megtalálható olyan területeken is, mint az alkalmazott matematika, a komplexitáselmélet, a kriptográfia, a kombinatorika és a számítógépes tudomány. Ez könnyen a logisztika legfontosabb problémája.
A hátizsák problémában az adott elemeknek legalább két attribútummal kell rendelkezniük - az elem értéke, amely befolyásolja annak fontosságát, és az elem súlya vagy térfogata, ami korlátozó szempontja. Mivel a teljes körű keresés nem lehetséges, a problémákat kisebb alproblémákra bonthatja és rekurzív módon futtathatja. Ezt optimális alszerkezetnek nevezik. Ez egyszerre csak egy elemre vonatkozik, és a hátizsákban még mindig elérhető a jelenlegi súly. A problémamegoldónak csak a még elfogadható súly alapján kell eldöntenie, hogy elveszi-e a terméket, vagy sem. Ha ez egy program, az újraszámítás nem független, és problémákat okozna. Itt alkalmazhatók dinamikus programozási technikák. Az egyes alproblémák megoldásait úgy tárolják, hogy a számításnak csak egyszer kell megtörténnie.
