NalogeTec/naloge01Nahrbtnik/Hladilna torba/Rešitev

Iz PSA
Skoči na: navigacija, iskanje

Torba hladilna1.jpg

V = (1, 1, 3, 3, 4)
C = (2, 10, 6, 8, 4)

Spremenljivke v spodnjih enačbah so:
Sj = {množica parov (V, C), ki opisuje G(i,W)} W – volumen, ki je še na voljo
Zj = {množica parov(V, C): (W-vj,C-cj) ε Sj-1}
Sj – zlitje(upoštevamo le maksimalno vrednost na vsakem odseku) Sj-1 in Zj

S0 = {(0,0)} /Še nimamo nobenega predmeta.
Z1 = {(0+1, 0+2)} = {(1, 2)} /Vstavimo prvo pijačo (1, 2).

S1 = {(0,0), (1, 2)} /Zlijemo S0 in Z1.
Z2 = S1 ‡ (1, 10) = {(0+1, 0+10), (1+1, 2+10)} = {(1, 10), (3, 12)} /Vstavimo drugo pijačo (1, 10).

S2 = {(0, 0), (1, 10), (3, 12)} /Zlijemo S1 in Z2 pri čemer na vsakem odseku upoštevamo le maksimalno vrednost.
Z3 = S2 ‡ (3, 6) = {(3, 6), (4, 16), (6, 18)} /Vstavimo tretjo pijačo (3, 6)

S3 = {(0, 0), (1, 10), (3, 12), (4, 16), (6, 18)} /Zlijemo S2 in Z3 pri čemer na vsakem odseku upoštevamo le maksimalno vrednost.

Z4 = S3 ‡ (3, 8) = {(3, 8), (4, 18), (6, 20), (7, 24), (9, 26)} /Vstavimo četrto pijačo (3, 8).

S4 = {(0, 0), (1, 10), (3, 12), (4, 18), (6, 20), (7, 24), (9, 26)}
/Zlijemo S3 in Z4 pri čemer na vsakem odseku upoštevamo le maksimalno vrednost.

Z5 = S4 ‡ (4, 4) = {(4, 4), (5, 14), (7, 16), (8, 22), (10, 24)...} /Vstavimo peto pijačo (4, 4). Gremo samo do prostornine 10, naprej nas ne zanima.

S5 = {(0, 0), (1, 10), (3, 12), (4, 18), (6, 20), (7, 24), (9, 26), (10, 24)...} /Zlijemo S4 in Z5 pri čemer na vsakem odseku upoštevamo le maksimalno vrednost.

Pare vodimo, dokler ne dosežemo prostornine, ki je na voljo V oz. (W*,C*) zadnji par v Sn, kjer je W* ≤ V

Če iščemo rešitev pri V = 10 je optimalna rešitev podana s parom (9, 26), saj imamo od para (10, 24) manjšo korist (C/V). V tem primeru smo v hladilno torbo dali naslednje predmete:

 Ker (9, 26) je ε S4, ni pa v Z5 : x5 = 0 SOK NISMO VZELI (-, -)

 Ker (9, 26) ni ε S3, je pa v Z4 : x4 = 1 PIVO SMO VZELI (3, 8)

(9, 26) smo dobili iz para (9, 26) – (3, 8) = (6, 18)

 Ker (6, 18) ni ε S2, je pa v Z3 : x3 = 1 VODO SMO VZELI (3, 6)

(6, 18) smo dobili iz para (6, 18) – (3, 6) = (3, 12)

 Ker (3, 12) ni ε S1, je pa v Z2 : x2 = 1 RED BULL SMO VZELI (1, 10)

(3, 12) smo dobili iz (3, 12) – (1, 10) = (1, 2)

 Ker (1, 2) ni ε S0, je pa v Z1: x1 = 1 KAVO SMO VZELI (1, 2)

Dobimo eno rešitev in sicer damo v nahrbtnik po vrsti predmete:

X = {1, 1, 1, 1, 0} oz. vzamemo kavo, red bull, vodo in pivo.

Nahrbtnik je zasedajo predmeti s prostorninami: 1 + 1 + 3 + 3 = 8

Nahrbtnik sicer ni polno zaseden, a boljše kombinacije kot ta, ki je vredna 2 + 10 + 6 + 8 = 26 ni mogoče dobiti.