knapsackoppgave

Knapsackoppgave er en klassisk problemstilling innen kombinatorisk optimering. Gitt en mengde objekter, hvert objekt har en vekt w i og en verdi v i. Målet er å velge en undergruppe av objekter slik at den totale vekten ikke overstiger kapasitetsgrensen W, og den totale verdien maksimeres.

Det finnes flere varianter. I 0/1-knapsack må hvert objekt velges helt eller ikke tatt (x i ∈ {0,1}). I fraksjonell knapsack kan man ta del av et objekt (0 ≤ x i ≤ 1). I ubegrenset knapsack kan man ta ubegrenset antall av hvert objekt (x i ∈ N_0). Den generelle formuleringen er å maksimere sum v i x i under sum w i x i ≤ W, med domene for x i avhengig av varianten.

Når det gjelder kompleksitet, er fraksjonell knapsack enkel å løse ved en greedy-sortering etter forholdet verdi/vekt. 0/1-knapsack er NP-hardt i generell form (beslutningsversjonen er NP-komplett), men kan løses i pseudo-polinomial tid med dynamisk programmering med tidskompleksitet O(nW) og minne O(nW). Ubegrenset knapsack kan også løses med DP i O(nW). Det finnes også andre metoder som branch-and-bound og møt-til-mitt for større instanser.

Knapsackoppgaven har bred anvendelse i ressursallokering, bagasje- og lastoptimalisering, budsjettfordeling og prosjektvalg i logistikk og produksjon. Den er også et grunnleggende eksempel i operasjonsanalyse og informatikkundervisning, og danner grunnlag for variasjoner og tilnærmingsteknikker som FPTAS for knapsack.