Preprosti problem nahrbtnika

Ponazoritev problema nahrbtnika

Preprosti problem nahrbtnika je računalniški problem, s katerim poskusimo zapolniti nahrbtnik z danimi predmeti, ki ima vsak svojo ceno in prostornino. Bodisi gre za dejansko polnjenje nahrbtnika, polnjenje nakupovalne vreče, 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.

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 $\sum _{i=1}^{n}c[i]*x[i]$ pri pogojih $\sum _{i=1}^{n}v[i]*x[i]\leq V$ in če je

• $0\leq x[i]\leq 1$
• $0<v[i]\leq V$
• $c[i]\;>0$.

Dopustna rešitev oziroma dopustna množica je v tem primeru kakršna koli množica rešitev $x=(x_{1},x_{2},...,x_{n})$, ki izpolnjuje te pogoje.

Optimalna rešitev pa je tista dopustna rešitev, pri kateri ima $\sum _{i=1}^{n}c[i]*x[i]$ največjo vrednost.

Postopek algoritma

Predmete najprej uredimo po vrednosti ${\frac {c[i]}{v[i]}}\geq {\frac {c[i+1]}{v[i+1]}};i=1,2,...,n$, 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$.

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)

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