0/1 nahrbtnik

0/1 nahrbtnik

Avtor: Tatjana Povše

Problem: Nakup nove programske opreme

Na šoli bi radi prenovili in dopolnili programsko opremo za računalniško učilnico. Za nakup nove programske opreme imajo na voljo 11.145 €. V učilnici je 15 računalnikov in vse računalnike morajo prenoviti enako, tako znese prenova programske opreme za 1 računalnik 743 €. Predlogi za novo programsko opremo so sledeči z vrednostjo pomembnosti programa:

(http://www2.nauk.si/files/333/seznamNahrbtnik.jpg)

Denar bi radi kar najbolje porabili za nakup opreme, da bi za dani znesek kupili opremo, ki jo najbolj potrebujemo.

0/1 nahrbtnik

Za na izlet v naravo, smo pripravili vse potrebne stvari kot so malica, voda, zemljevid, dežnik, dodatna oblačila… Ko jih želimo zložiti v nahrbtnik, ugotovimo, da ne moremo spraviti vseh vanj. Odločimo se, da bomo vzeli le najnujnejše stvari, ki jih bomo še lahko spravili v nahrbtnik. V ta namen predmete razvrstimo po pomembnosti in prostornini.

V našem problemu nam prostornino nahrbtnika predstavlja dani znesek, ki ga imamo na voljo:

(http://www2.nauk.si/files/333/ena1a.jpg)

Glede na ceno razvrstimo tudi programske opreme:

(http://www2.nauk.si/files/333/ena2a.jpg)

Predmete oz. programske opreme lahko jemljemo le cele (ne moremo jih kupovati po delih). Kot rešitev iščemo vrednosti

(http://www2.nauk.si/files/333/ena3.jpg)

, ki nam povedo, če bomo i-ti predmet spakirali v nahrbtnik oz. če bomo kupili i-to programsko opremo. Tako mora veljati pogoj:

(http://www2.nauk.si/files/333/ena4.jpg)

Ta pogoj pomeni, da mora biti skupna prostornina predmetov vi s frekvenco xi, ki jih lahko zložimo v nahrbtnik, manjša ali enaka prostornini nahrbtnika.

Metoda z zlivanjem

Za 0/1 nahrbtnik velja pravilo optimalnosti, ki pravi, da je zaporedje odločitev optimalno, če in samo če je tudi vsako podzaporedje tega zaporedja odločitev tudi samo optimalno.

Za vsak predmet, ki bi ga radi dali v nahrbtnik, poiščemo vse možne rešitve, to pomeni kombinacije nabora predmetov. Nato se po pravilu optimalnosti odločimo ali rešitev sprejmemo ali zavržemo. Najbolj optimalna je tiste kombinacija predmetov, ki pri dani skupni vsoti točk pomembnosti predmetov, zavzema manjšo prostornino v nahrbtniku.

Z G(i,W) označimo vrednost posamezne optimalne rešitve, s predmeti z indeksi od 1 do i in prostim volumnom W.

Predmet (vi, ci) zavržemo, kot neuporabno možno rešitev:

  • če smo že (s predmeti 1 .. i-1) smo sestavili optimalno rešitev za ta volumen: G(i-1,W)
  • prej (s predmeti 1 .. i-1) smo morali poznati optimum za nahrbtnik z vi manjšim volumnom: G(i-1, W-vi) in če ne ustreza pogoju zapisanim z Bellmanovo enačbo:
(http://www2.nauk.si/files/333/bellova.jpg)

Rešitev z zlivanjem - 1

Uredimo programske opreme s cenami in pomembnostjo nakupa v urejen seznam, zaradi lažjega postopka, da lažje primerjamo rezultate med seboj; pa tudi končni rezultat je nazoren urejen seznam; urejenost seznama pa ne vpliva na izid rešitve:

( vi, ci ) prva vrednost je cena v €, druga pa pomembnost nakupa

(29,2), (32,6) ,(127,4),(142,7),(516,5)

Na vsakem koraku tvorimo množico S, ki vsebuje vse optimalne rešitve - nakupe. Na začetku ima množica en element z vrednostjo nakupa 0 € in pomembnostjo 0.

S0 = {(0,0)} Prazen seznam za nakup

Nato tvorimo na vsakem koraku množico vseh možnih rešitev Z - nakupov tako, da tvorimo nove kombinacije nakupov z novim elementom - programsko opremo. V tej množici so tudi neoptimalne rešitve, ko te zavržemo tvorimo množico S za naslednji korak postopka.

Z1 = {(29,2)} Vzamemo prvo programsko opremo (29,2) in tvorimo možne kombinacija seznama za nakup z dodajanjem nove programske opreme

Zlijemo skupaj S0 in Z1, oziroma izberemo iz obeh seznamov optimalne možnosti, slabe pa zavržemo,:

S1 = {(0,0),( 29,2)}

Postopek ponovimo tudi pri drugih programskih opremah. Vzamemo drugo programsko opremo (32,6):

Z2 = {(32,6),(61,8)}

Zlijemo skupaj S1 in Z2:

S2 = {(0,0) ,(29,2),( 32,6),(61,8)}

Vzamemo tretjo programsko opremo (127,4):

Z3 = {(127,4),(156,6),(159,10),(188,12)}

Zlijemo skupaj S2 in Z3:

S3 = {(0,0) ,(29,2),( 32,6),(61,8) ,(159,10),(188,12)}

Možnost polnjenja seznama za nakup za (127,4), pri skupnem znesku 127 € znese le vrednosti pomembnosti 4, ker je slabša možnost od polnitve seznama (61,8), ki ima pri manjšem znesku 61 € večjo vrednost pomembnosti 8. Možnost (127,4) zavržemo. Prav tako zavržemo polnitev seznama (156,6). To pravilo upoštevamo, če je potrebno pri zlivanju v nadaljnjih korakih.

Rešitev z zlivanjem - 2

Vzamemo četrto programsko opremo (142,7):

Z4 = {(142,7),(171,9),(174,13),(203,15),(301,19)}

Zlijemo skupaj S3 in Z4:

S4 = {(0,0) ,(29,2),( 32,6),(61,8) ,(159,10),(174,13),(203,15),(301,19)}

Vzamemo peto programsko opremo (516,5):

Z5 = {(516,5),(545,7),(548,11),(577,13),(675,15),(690,18),(719,20),(817,24)}

Zlijemo skupaj S4 in Z5:

S5 = {(0,0) ,(29,2),( 32,6),(61,8) ,(159,10),(174,13),(203,15),(301,19), (719,20),(817,24)}

Tako dobimo, da je optimalna rešitev 719 € pri pomembnosti 20. Zakaj pa ni rešitev (817, 24). In optimalna rešitev je le 20!!! Namreč to je maksimalno zadovoljstvo, ki ga lahko dosežete, če ne smete porabiti več kot 743 €. Rešitev (817,24) bi bila ustrezna, če bi imeli na voljo za nakup programske opreme 817 € ali več.

Seznam S5 nam prestavlja optimalne polnitve seznamov za nakup, torej funkcijo G(W), kjer je W skupni volumen predmetov oz. skupni strošek za nakup programov.

(http://www2.nauk.si/files/333/graf.jpg)

Rešitev z zlivanjem - 3

Sedaj moramo dobiti še rešitev x. Z (W*,C*) označimo zadnji par v Sn, za katerega velja W* ≤ V. Torej v W* imamo skok na C*, kar pomeni, da je to skok v Sn-1 ali pa v Zn. V prvem primeru je xn = 1, v drugem pa xn = 0. Če imamo skok iz Sn v Sn-1, pomeni da je par oz element tvoril z drugimi elementi optimalno rešitev. Če pa imamo skok iz Sn v Zn, pomeni da je par oz element ni tvoril z drugimi elementi optimalne rešitve in ni bil izbran v Sn. Če je (W*,C*) tako v Sn − 1 kot v Zn, pomeni to, da obstajata dve optimalni rešitvi z isto vrednostjo in isto skupno velikostjo, od katerih ena vsebuje zadnji predmet, druga pa ne. Odločimo se lahko za prvo ali drugo možnost. Ko poznamo komponento xn, nadaljujemo na enak način z določanjem vrednosti za xn − 1, kjer v primeru xn = 1 vrednost tekočega skoka zmanjšamo v (W*,C*) -> (W*- vn,C* - cn).

Postopek ponavljamo, da poiščemo vse vrednosti xi , i = n, n-1, …,1:

(719,20) ni element S4 -> x5 = 1 : skok(719,20), (516,5) je element S4

(203,15) ni element S3 -> x4 = 1 : (203,15), (142,7) je element S3

(61,8) je element S2 -> x3 = 0

(61,8) ni element S1 -> x2 = 1 : (61,8), (32,6) je element S2

(29,2) ni element S0 -> x1 = 1

Izmed programske opreme: V = {(29,2), (32,6) ,(127,4),(142,7),(516,5))

bomo postavili na seznam nakupa programske opreme, ki imajo x enak 1.

X = (1,1,0,1,1)

Seznam nakupa programske opreme:

  • Operacijski sistem Windows7 Professional 32-bit DSP SLO 142 €
  • Protivirusni zaščitni program ESET NOD32 32 €
  • FotoSlate 4.0 Photo Print Studio 29 €
  • Adobe Dreamweaver CS6 516 €

Od razpoložljivih 743 € bomo porabili za nakup programske opreme 719 €, ostalo pa bo le 24 € na vsak računalnik.

Za 15 računalnikov bomo od razpoložljivih 11.145 € porabili za nakup 10.785 €, ostalo pa bo 360 €.

Literatura

0%
0%