Indhold
- Definition - Hvad betyder rygsækproblem?
- En introduktion til Microsoft Azure og Microsoft Cloud | Gennem denne vejledning lærer du, hvad cloud computing handler om, og hvordan Microsoft Azure kan hjælpe dig med at migrere og drive din virksomhed fra skyen.
- Techopedia forklarer Knapsack Problem
Definition - Hvad betyder rygsækproblem?
Rygsækproblemet er et optimeringsproblem, der bruges til at illustrere både problem og løsning. Det henter sit navn fra et scenarie, hvor man er begrænset i antallet af emner, der kan placeres i en rygsæk i fast størrelse. Givet et sæt varer med specifikke vægte og værdier, er målet at få så meget værdi i rygsækken som muligt i betragtning af rygsækets vægtbegrænsning.
En introduktion til Microsoft Azure og Microsoft Cloud | Gennem denne vejledning lærer du, hvad cloud computing handler om, og hvordan Microsoft Azure kan hjælpe dig med at migrere og drive din virksomhed fra skyen.
Techopedia forklarer Knapsack Problem
Rygsækproblemet er et eksempel på et kombinationsoptimeringsproblem, et emne i matematik og datalogi om at finde det optimale objekt blandt et sæt objekter. Dette er et problem, der er blevet undersøgt i mere end et århundrede og er et almindeligt anvendt eksempel problem i kombinatorisk optimering, hvor der er behov for et optimalt objekt eller en endelig løsning, hvor en udtømmende søgning ikke er mulig. Problemet kan findes i virkelighedsscenarier som ressourcetildeling i økonomiske begrænsninger eller endda ved valg af investeringer og porteføljer. Det kan også findes inden for områder som anvendt matematik, kompleksitetsteori, kryptografi, kombinatorik og datalogi. Det er let det vigtigste problem inden for logistik.
I rygsækproblemet har de givne varer mindst to attributter - en vares værdi, der påvirker dens betydning, og en vares vægt eller volumen, som er dets begrænsningsaspekt. Da en udtømmende søgning ikke er mulig, kan man opdele problemerne i mindre underproblemer og køre det rekursivt. Dette kaldes en optimal understruktur. Dette omhandler kun et emne ad gangen og den aktuelle vægt stadig tilgængelig i rygsækken. Problemløseren behøver kun at beslutte, om varen skal tages eller ej på baggrund af den vægt, der stadig kan accepteres. Hvis det imidlertid er et program, er genberegning ikke uafhængig og vil medføre problemer. Det er her, dynamiske programmeringsteknikker kan anvendes. Løsninger til hvert underproblem gemmes, så beregningen kun behøver at ske en gang.