Innholdsfortegnelse:
Definisjon - Hva betyr ryggsekkproblem?
Ryggsekkproblemet er et optimaliseringsproblem som brukes til å illustrere både problem og løsning. Det henter navnet fra et scenario der man er begrenset i antall elementer som kan plasseres i en ryggsekk i fast størrelse. Gitt et sett med gjenstander med spesifikke vekter og verdier, er målet å få så mye verdi inn i ryggsekken som mulig gitt vektbegrensningen til ryggsekken.
Techopedia forklarer Knapsack Problem
Ryggsekkproblemet er et eksempel på et kombinasjonsoptimaliseringsproblem, et tema i matematikk og informatikk om å finne det optimale objektet blant et sett med objekter. Dette er et problem som har blitt studert i mer enn et århundre og er et ofte brukt eksempel problem i kombinatorisk optimalisering, der det er behov for en optimal objekt eller en begrenset løsning der et uttømmende søk ikke er mulig. Problemet kan finnes i virkelige scenarier som ressursfordeling i økonomiske begrensninger eller til og med ved valg av investeringer og porteføljer. Det kan også finnes innen felt som anvendt matematikk, kompleksitetsteori, kryptografi, kombinatorikk og informatikk. Det er lett det viktigste problemet innen logistikk.
I ryggsekkproblemet har de gitte elementene minst to attributter - en vares verdi, som påvirker dens betydning, og en vares vekt eller volum, som er dens begrensningsaspekt. Siden et uttømmende søk ikke er mulig, kan man dele problemene i mindre delproblemer og kjøre det rekursivt. Dette kalles en optimal understruktur. Dette omhandler bare ett element av gangen, og den gjeldende vekten fremdeles tilgjengelig i ryggsekken. Problemløseren trenger bare å bestemme om du vil ta varen eller ikke, basert på vekten som fremdeles kan aksepteres. Imidlertid, hvis det er et program, er ikke beregning ikke uavhengig og vil føre til problemer. Det er her dynamiske programmeringsteknikker kan brukes. Løsninger på hvert delproblem lagres slik at beregningen bare trenger å skje en gang.
