Kazalo:
Opredelitev - Kaj pomeni težava z nahrbtnikom?
Problem nahrbtnika je težava z optimizacijo, ki se uporablja za ponazoritev problema in rešitve. Ime je dobila po scenariju, kjer je eden omejen na število predmetov, ki jih je mogoče namestiti v nahrbtnik fiksne velikosti. Glede na nabor predmetov z določenimi utežmi in vrednostmi je cilj doseči čim večjo vrednost v nahrbtniku glede na omejitev teže nahrbtnika.
Tehopedia razlaga težavo z nahrbtnikom
Problem nahrbtnika je primer problema kombinirane optimizacije, teme iz matematike in računalništva o iskanju optimalnega predmeta med naborom predmetov. To je težava, ki se je proučevala že več kot stoletje in je pogosto uporabljen primer težave pri kombinatorni optimizaciji, kjer je potrebna optimalna stvar ali končna rešitev, kjer izčrpno iskanje ni mogoče. Težavo lahko najdemo v resničnih scenarijih, kot je razporejanje virov v finančnih omejitvah ali celo pri izbiri naložb in portfeljev. Najdemo ga tudi na področjih, kot so uporabna matematika, teorija zapletenosti, kriptografija, kombinatorika in računalništvo. To je enostavno najpomembnejša težava v logistiki.
V težavi z nahrbtnikom imajo dani predmeti vsaj dva atributa - vrednost predmeta, ki vpliva na njegov pomen, in teža ali obseg predmeta, ki je njegov vidik omejevanja. Ker izčrpno iskanje ni mogoče, lahko težave razbije na manjše podprobleme in jih sproži rekurzivno. Temu pravimo optimalna podstruktura. Ta obravnava samo en predmet hkrati in trenutno težo, ki je še vedno na voljo v nahrbtniku. Reševalec težav se mora le odločiti, ali bo predmet vzel ali ne, glede na težo, ki jo je še mogoče sprejeti. Če pa gre za program, ponovno računanje ni neodvisno in bi povzročilo težave. Tu se lahko uporabljajo dinamične tehnike programiranja. Rešitve za vsak podproblem so shranjene tako, da bi bilo treba izračunati samo enkrat.
