Rešitev: Optimalno napolni preprosti nahrbtnik

Iz MaFiRaWiki

Naloga: Optimalno napolni preprosti nahrbtnik

  • Najprej preverimo ali je vsota vseh vrednosti predmetov večja kot velikost nahrbtnika. Če ne bi bila, bi v nahrbtnik dali kar vse predmete. Vsota vseh velikosti predmetov je 30, kar pa je večje kot 17.
  • Predmete uredimo po njihovih dragocenostih od največje do najmanjše. Dragocenost je razmerje med njegovo vrednostjo in njegovo velikostjo. Dragocenosti predmetov: d1=6/4, d2=4/2, d3=5/6, d4=8/6, d5=4/4, d6=9/8 uredimo od največje do najmanjše: d2,d1,d4,d6,d5,d3.
  • Predmete vstavljamo v nahrbtnik od najdragocenejšega do najmanj dragocenejšega, pri tem pa pazimo, da vsota velikosti predmetov, ki so v nahrbtniku ne preseže velikosti nahrbtnika.
  • Najprej damo v nahrbtnik najdragocenejši predmet, se pravi predmet x2. Vsota velikosti predmetov v nahrbtniku je kar velikost predmeta x2, to je 2. Ker je 2 manjše kot 17, v nahrbtnik vstavimo cel predmet x2 in postopek nadaljujemo.
  • Drugi najdragocenejši predmet je x1. Vstavimo ga celega v nahrbtnik. Vsota velikosti predmetov v nahrbtniku je sedaj 6. 6 je manjše kot 17, zato s postopkom nadaljujemo.
  • Podobno kot prej v nahrbtnik vstavimo cel predmet x4. Sedaj je vsota velikosti predmetov v nahrbtniku 12.
  • Ker je v nahrbtniku le še 17-12 = 5 enot prostora, na bomo mogli naslednjega predmeta, to je x6, velikega 8, celega vstaviti vanj. Zato ga bomo vzeli le del, in sicer 5/8.
  • Vsota velikosti predmetov v nahrbtniku je sedaj 17, nahrbtnik je poln, zato postopek zaključimo. Rešitev podamo v obliki vektorja x = (1,1,0,1,0,5/8). Maksimalna vsota vseh vrednosti predmetov v nahrbtniku je 189/8.

Glej tudi

Osebna orodja