# Zadanie 8 AiSD
Na podstawie: https://www.cs.cornell.edu/~kozen/Papers/change.pdf
Niech ALG(x) - ilość monet w reprezentacji liczby x dla nominałów {$1,a,b$} powstałych podczas algorytmu zachłannego.
OPT(x) - ilość monet w reprezentacji liczby x dla nominałów {$1,a,b$} powstałych podczas algorytmu optymalnego.

Niech x to reszta do wydania.
Niech $b = q\cdot a + r$ gdzie $0 \leq r < a$.
***Twierdzenie:*** Algorytm zachłanny jest gorszy(nie jest optymalny) niż optymalny $\iff$ $0 < r < a - q$.
##### Dowód:
$<=$ Musimy pokazać, że jeśli $0 < r < a - q$ to istnieje taki kontrprzykład, że algorytm zachłanny jest gorszy od OPT. Niech $x = a + b - 1$. Wtedy ALG( x ) weźmie jedno b, następnie a-1 razy 1, łącznie a-1 + 1 = a elementów. OPT ( x ) weźmie 0 elementów b, q+1 elementów a, r-1 jedynek, ponieważ wtedy $0*b + (q+1)*a + (r-1)*1 = qa + a + r - 1 = a + b - 1$, wtedy mamy łącznie (q+1) + (r-1) = q+r, ale z założenia, że $0<r<a-q <=> r+q<a$ otrzymujemy, że OPT wziąl mniej elementów niż zachłannym, więc ALG jest gorszy niż OPT.

---

***Aby udowodnić implikację w drugą stronę potrzebne będą nam następujące lematy:***

***Lemat 1:***
Dla każdego $x$ oraz dowolnej monety $c_i \in${$1,a,b$} zachodzi nierówność:
$OPT(x) \leq OPT(x-c_i) + 1$
Dowód: optymalna reprezentacja $x$ w najlepszym przypadku powstanie poprzez dodanie do optymalnej reprezentacji $x-c_i$ monety $c_i$, zatem nierówność zachodzi.

Zauważamy, że równość $OPT(x) = OPT(x-c_i) + 1$ zajdzie wtedy i tylko wtedy gdy istnieje optymalna reprezentacja $x$ używając monety $c_i$.

---

***Lemat 2:***
Jeżeli istnieje kontrprzykłąd $x$, to najmniejszy taki $x$ spełania nierówność:
$b+1 < x < b+a$ czyli $x \in [b+2, b+a-1]$.
Dowód:
Załóżmy, że $ALG$ jest niepoprawny (strategia zachłanna jest nieoptymalna).
Ograniczenie dolne:
1. jeśli $x<b$ to $OPT(x) = ALG(x)$ bo mamy do wyboru nominały {$1,a$}, więc x nie może być kontrprzykładem.
2. jeśli $x=b$ wtedy $ALG(x) = OPT(x) = 1$ bo wydamy jedną monete $b$.
3. jeśli $x=b+1$ to $ALG(x) = OPT(x)$ bo wydamy jedną monete $b$ oraz jedną monete $1$.
wynika stąd, że x > b+1

Ograniczenie górne:
niech $x\geq b+a$ oraz załóżmy, że dla dowolnego $t < x$ $OPT(t) = ALG(t)$, czyli, że algorytm zachłanny jest optymalny dla dowolnej liczby mniejszej niż x.
1. jeśli moneta $b$ jest w reprezentacji optymalnej to $ALG(x) = ALG(x-b) + 1$ z założenia $= OPT(x-b) +1$ z lematu 1 $=OPT(x)$.
2. jeśli moneta $a$ jest w reprezentacji optymalnej to $ALG(x) = ALG(x-b)+1 = OPT(x-b) + 1 \leq OPT(x-b-a) + 1 + 1 = OPT(x-b-a) + 2 \leq ALG(x-b-a) + 2 = ALG(x-a) + 1 = OPT(x-a) + 1 = OPT(x)$ ale wiemy, że $OPT(x) \leq ALG(x)$, zatem otrzymujemy $ALG(x)\leq OPT(x) \leq ALG(x) => OPT(x) = ALG(x)$.
3. jeśli moneta $1$ jest w reprezentacji optymalnej to analogicznie jak w 2. tylko $a:=1$.

Podsumowując, otrzymujemy, że jeśli $x \geq b+a$ i dla dowolnego $t < x$ $OPT(t) = ALG(t)$ to $OPT(x) = ALG(x)$, zatem musi istnieć kontrprzykład $x<b+a$ jeżeli strategia zachłanna ma być niepoprawna.

---
$=>$ Załóżmy, że algorytm zachłanny nie jest optymalny. Z lematu 2 wiemy, że najmniejszy kontrprzykład $x \in [b+2; a+b-1]$. Nasz ALG wybierze elementy:
$1-b$, $0-a$, $e-1$, gdzie $e\in[1,a-1]$, czyli łącznie e+1 monet.
Zauważmy, że $OPT$ nie może wziąć ani jednego $b$, wtedy byłby taki sam jak $ALG$. Zatem niech $OPT$ weźmie $0-b$, $k-a$, $j-1$. Zauważmy, że tak naprawdę $j$ musi być równe $0$. Wynika to stąd, że jeśli $j\neq0$ to istnieje optymalna reprezentacja $x$ używając monety $1$, zatem z lematu 1 $OPT(x) = OPT(x-1) + 1$ więc $OPT(x-1)= OPT(x) - 1 => OPT(x-1) < OPT(x)$ i analogicznie $OPT(x-j) < OPT(x)$ więc $x-j$ byłoby mniejszym kontrprzykładem od $x$, ale założyliśmy, że $x$ jest najmniejszym, więc $j=0$. Finalnie $OPT$ składa się z $k - a$, więc $x = k\cdot a = b + e \cdot 1 => b = ka - e => (k-1)a + (a-e)$, stąd $q= k-1$, $r = a-e$.
zauważmy, że skoro $ALG(x)$ ma $e+1$ monet, oraz $OPT(x)$ ma k monet to $k<e+1 => k-1 < e$, ponieważ założyliśmy, że $ALG$ jest gorszy niż $OPT$.
Skoro $e\in [1,a-1]$ to $0<a-e<a$ ale $k-1< e$ więc $1-k > -e$ czyli $0<a-e<a+1-k= a - q$ więc $0<a-e<a-q <=> 0<r<a-q$, co kończy dowód.

Algorytm:

r = b % a
q = (int) b/a
if 0<r<a-q return true;
else return false;