4736387704

Stosując tę samą strategię kupujemy sztabkę 2 uncjową, 1 uncjową oraz 0,5 uncjową. Zauważmy, że otrzymaliśmy optymalne rozwiązanie.

Uwaga. W tego typu problemach opisana powyżej metoda zachłanna nie zawsze daje rozwiązanie optymalne. Ilustruje to poniższy przykład.

2. Mamy do dyspozycji następujące opakowania towaru X: 1 sztuka, 20 sztuk oraz 70 sztuk. Chcemy nabyć 80 sztuk towaru X w jak najmniejszej liczbie opakowań. Jeżeli będziemy stosować metodę opisaną w poprzednim zadaniu, to wybierzemy: 1 opakowanie - 70 sztuk oraz 10 opakowań - 1 sztuka; czyli razem 11 opakowań. Optymalnym wyborem jednak są 4 opakowania - 20 sztuk.

6.2. Zadania

1.    W kasie sprzedawca ma do dyspozycji monety o następujących nominałach Co — 1, Ci — 2, C3 — 5, C4 — 10, C5 — 20. Sprzedawca musi wydać resztę w wysokości s = 345 (odp. s = 435, s = 23, s = 1241). Zakładamy, że do dyspozycji jest nieograniczona liczba monet każdego nominału. Sprzedawca chce wydać resztę wykorzystując jak najmniejszą liczbę monet. Których i ile monet musi użyć?

(a)    Opracować metodę zachłanną, która rozwiąże ten problem.

(b)    Czy ta metoda w naszej sytuacji daje optymalne rozwiązanie problemu? Odpowiedź uzasadnić.

(c)    Jakie problemy pojawiają się, gdy zrezygnujemy z założenia o nieograniczonej liczbie monet każdego nominału?

(d)    Skonstruować przykład, w którym nasza metoda nie daje optymalnego rozwiązania.

2.    W bankomacie są do dyspozycji banknoty o następujących nominałach Cq = 20, Ci = 50, C3 = 100, C4 = 200. Bankomat musi wypłacić kwotę s = 3450 (odp. s = 4350, s = 2340, s = 1270). Zakładamy, że do dyspozycji jest nieograniczona liczba banknotów każdego nominału. Bankomat powinien wypłacać pieniądze wykorzystując jak najmniejszą liczbę banknotów. Których i ile banknotów musi użyć?

(a)    Czy bankomat będzie w stanie wypłacić każdą kwotę? Jakie kwoty możemy wypłacić z tego bankomatu, a jakich nie?

(b)    Rozwiązać analogiczne problemy do tych opisanych w poprzednim zadaniu.

7