Preprosti nahrbtnik

Iz MaFiRaWiki

Problem preprostega nahrbtnika je računalniški problem, kjer skušamo napolniti nahrbtnik z volumnom V z n predmeti, katerih skupna vsota velikosti \sum_{i=1}^n v[i] je večja od volumna nahrbtnika, tako, da bo vrednost nahrbtnika optimalna.

Velikost i-tega predmeta najprej označimo z v[i], ceno pa s c[i], za vsak i{1,...n} pa mora veljati tudi c[i] > 0 in v[i] > 0.

Problema se lotimo tako, da razporedimo predmete po relativni vrednosti \frac{c[i]}{v[i]} (dragocenosti) po vrstnem redu od največjega do najmanjšega. Zatem po vrsti jemljemo tako urejene predmete, dokler ne napolnimo nahrbtnika (požrešna metoda glede na dragocenost). Za razliko od O/1 nahrbtnika, lahko pri polnjenju preprostega nahrbtnika predmete celo režemo, zato zadnjega, ki ga ne moremo v celoti dati v nahrbtnik, ustrezno prerežemo. Od tod vidimo, da sme biti v nahrbtniku le en razrezan predmet.

Rezultat dobimo v obliki seznama, v katerem so podani deleži elementov nahrbtnika. Delež i-tega elementa označimo z x[i]. Če je vrednost x[i] enaka 0 pomeni, da v nahrbtniku tega elementa ni, če je vrednost 1, smo ta predmet uspeli v celoti dati v nahrbtnik, če pa je 0 < x[i] < 1 pa smo predmet morali razrezati, torej je v nahrbtniku le del tega predmeta.

Pa poglejmo še primer:

Navodilo: Optimalno napolni nahrbtnik s podatki:

M = 17 (*velikost oz. volumen nahrbtnika*)
n = 6 (*število predmetov*)
v = {4, 2, 6, 6, 4, 8} (*velikosti predmetov*)
c = {6, 4, 5, 8, 4, 9} (*cene predmetov*)

Najprej preverimo, ali je vsota velikosti predmetov večja, kot velikost nahrbtnika:

If[Apply[Plus, v] > M, Print["Vsota podatkov, s katerimi želimo napolniti nahrbtnik, je večja 
kot je velikost nahrbtnika, zato uporabimo požrešno metodo."], Print["Vsi podatki gredo v 
nahrbtnik, zato ni potrebno uporabiti požrešne metode."]]

Kot lahko vidimo, je vsota velikosti predmetov res večja, kot je volumen nahrbtnika, zato nam prejšna funkcija vrne

Vsota podatkov, s katerimi želimo napolniti nahrbtnik, je večja kot je velikost nahrbtnika, 
zato uporabimo požrešno metodo.

Definiramo nekaj funkcij, ki jih bomo potrebovali v algoritmu:

vsota = 0 (* funkcija, ki šteje velikosti predmetov, ki jih dajemo v nahrbtnik*)
delezi = Table[0, {i, Length[v]}] (*funkcija, ki nam pove, kakšni so deleži elementov v 
nahrbniku. Na začetku tej funkciji upriredimo same ničle, kasneje pa jih zamenjamo z 
ustreznimi deleži.*)
dragocenost = c/v (*seznam dragocenosti predmetov*)

V naslednjem koraku iščemo predmete, ki jih lahko v celoti damo v nahrbtnik. Pri iskanju najbolj dragocenega predmeta, namesto raporejanja po velikosti, uporabimo kar vgrajeni ukaz Max, ki nam prav tako vrne najbolj vreden predmet. Po vsakem koraku ustrezno spremenimo tudi funkcije vsota, dragocenost in delezi.

While[vsota < M,
 p = Position[dragocenost, Max[dragocenost]];
 vsota = vsota + Part[v, Flatten [p]][[1]];
 dragocenost = ReplacePart[dragocenost, 0, p];
 delezi = ReplacePart[delezi, 1, p]
 ]

Od tod torej dobimo vse predmete, ki so v celoti v nahrbtniku, vključno s tistim, ki sicer ni v celoti v njem. Le tega je sedaj potrebno ustrezno prerezati. To storimo v naslednjem koraku.

If [vsota > M,
 razlika = vsota - M;
 delezi = ReplacePart[delezi,(Part[v, Flatten [p]][[1]] - razlika)/
 Part[v, Flatten[p]][[1]], p];
 Print["Deleži podatkov, s katerimi smo polnili nahrbtnik:" , delezi], delezi = delezi; 
 Print["Deleži podatkov, s katerimi smo polnili nahrbtnik: " , delezi]
 ]

Zgornji korak nam vrne tudi rezultat. V tem primeru se izpiše

Deleži podatkov, s katerimi smo polnili nahrbtnik: {1, 1, 0, 1, 0, \frac{5}{8}}.

Glej tudi

Osebna orodja