From Wikipedia, the free encyclopedia
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.
Ta članek potrebuje čiščenje. Pri urejanju upoštevaj pravila slogovnega priročnika. |
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.
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
Dopustna rešitev oziroma dopustna množica je v tem primeru kakršna koli množica rešitev , ki izpolnjuje te pogoje.
Optimalna rešitev pa je tista dopustna rešitev, pri kateri ima največjo vrednost.
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 .
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)
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
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.