Ryggsekkproblemet

Ressurser: 15.2 page=568 Engelsk - knapsack problem

Det kontinuerlige ryggsekproblemet

Gitt $n$ ulike beholdere med ulike væsker oppi, der hver væske har en verdi per liter $v_1,\dots ,v_n$ og beholderne har volum $w_1,\dots ,w_n$. Du skal fylle en bøtte med volum $W$ til toppen s.a du maksimerer verdien i bøtten du fyller. Dette problemet man løses med grådighet. Her kan vi rett og slett fylle så mye som mulig av beholderen med høyest verdi per liter, enten til beholderen blir tom eller bøtten blir full. Hvis beholderen blir tom fortsetter vi med den mest verdifulle væsken etc. helt til bøtten vår er full.

Det binære ryggsekkproblemet

Dette er et vanskeligere problem. Det ligger totalt $n$ gjenstander som kan puttes i sekken. Hver gjenstand $i$ har en vekt $w_i$ og en verdi $v_i$. Vi ønsker å maksimere verdien av gjenstander i ryggsekken uten å overstige vektkapasiteten. Der $W$ er vektkapasiteten, $n$ er antall objekter, og $w_1,\dots ,w_n$ og $v_1,\dots ,v_n$ er globale variabler.