Preprosti problem nahrbtnika
Iz Wikipedije, proste enciklopedije
|
Ta članek (oz. del članka) je slogovno neurejen. Pomagajte nam ga urediti. Po končanem delu sporočilo odstranite. |
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
.
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