Preprosti problem nahrbtnika
Iz Wikipedije, proste enciklopedije
Preprosti problem nahrbtnika je računalniški problem, s katerim probamo zapolniti nahrbtnik z danimi predmeti, ki ima vsak svojo ceno in prostornino. Bodisi gre za dejansko polnjenje nahrbtnika, polnjenje nakupovalne vrečne, zlaganje predmetov v avto. Deluje po principu, da bi karseda najbolje zapolnili prostor in vzeli dražje predmete s seboj.
Slabo polnjenje nahrbtnika je takrat, ko kar po vrsti polnimo nahrbtnik. Nahrbtnik bo hitro napolnjen in v njem je lahko samo en predmet, ki je sam po sebi sicer pomemben, zasede pa toliko prostora, da če bi dali namesto njega druga dva predmeta, ki sta manj pomembna, bi imeli več od vsebine nahrbtnika. Torej predmete najprej uredimo po njihovi pomembnosti in po prostoru, ki ga zasedejo.
Vsebina |
[uredi] Opis problema
Imamo nahrbtnik s podano prostornino V in n predmetov, pri čemer za vsak predmet svojo vrednost C[i] in prostornino v[i]. V nahrbtnik želimo straviti predmete dokler je v njem še kaj prostora in po načelu, da je v nahrbtniku čim večja vrednost. Predmete lahko režemo
pri pogojih
in če je
![0 \le x[i] \le 1](../../../math/f/5/b/f5bb9cec7f8c876bd7ba66ada42dbf4b.png)
![0 < v[i] \le V](../../../math/4/6/4/4646e88565f665fddc2fa8004be207aa.png)
.
Dopustna rešitev oziroma dopustna množica je v tem primeru kakršna koli množica rešitev x = (x1,x2,...,xn), ki izpolnjuje te pogoje.
Optimalna rešitev pa je tista dopustna rešitev, pri kateri ima
največjo vrednost.
[uredi] Postopek algoritma
Predmete najprej uredimo po vrednosti
, torej od največje vrednosti do najmanjše. Nato pa dajemo predmete v nahrbtnik, dokler gredo celi vanj. Ko naletimo na prvi predmet, ki ne gre več v nahrbtnik, ga režemo in sicer tako, da nahrbtnik napolnimo, ostale predmete pa ne damo v nahrbtnik, torej je x[i] = 0.
[uredi] Zahtevnost
Zanka se izvrši največkrat n krat, saj lahko v skrajnjem primeru damo v nahrbtnik vseh n predmetov, zato je časovna zahtevnost tega algoritma O(n)
[uredi] Splošna procedura
procedure Napolni (V, n, v, c, x)
begin
for i:= 1 to n do
x[i] := 0
prostor := V
i := 1
repeat
if v[i] > prostor then
exit (repeat)
else
begin
x[i] := 1 // i-ti predmed se gre v nahrbtnik
prostor := prostor - v[i]
end
i:= i + 1
until i>n
if i<=n then
x[i] := prostor / v[i] //prvi predmet, ki ne gre cel noter, razdelimo
end

