Sia \(S=\{ 1, 2, .., n \}\) un insieme di intervalli della retta reale. Ogni intervallo \([a_i, b_i)\), con \(i\in S\), e' chiuso a sinistra e aperto a destra con \(a_i\) tempo di inizio e \(b_i\) tempo di fine. Un insieme indipendente massimale e' un sottoinsieme di massima cardinalità formato da intervalli tutti disgiunti tra loro.

Possiamo risolvere questo problema con la programmazione dinamica, oppure possiamo dimostrare che esiste una scelta ingorda che porta alla soluzione ottima. Vediamo entrambi gli approcci

Set independentSet(int[] a, int[] b)
  {ordina a e b in modo che b[1] <= b[2] <= .. <= b[n]}
  Set S = Set()
  S.insert(1)
  int last = 1
  for i=2 to n do
    if a[i]>=b[last] then
      S.insert(i)
      last = i
  return S

Dato un'insieme di "tagli" di monete memorizzati in un vettore di interi positivi \(t[1..n]\) e un intero \(R\) rappresentante il resto che dobbiamo restituire. Trovare il più piccolo numero intero di pezzi necessari per dare un resto di \(R\) centesimi utilizzando i tagli disponibili, assumendo di avere un numero illimitato di monete per ogni taglio. Formalmente, trovare un vettore \(x\) di interi non negativi tale che \(R=\sum_{i=1}^n x[i]t[i]\) e \(m=\sum_{i=1}^nx[i]\) ha valore minimo.

Risolviamo prima il problema con la programmazione dinamica. Sottostruttura ottima: Sia \(S(i)\) il problema di dare un resto pari ad \(i\). Sia \(A(i)\) una soluzione ottima del problema \(S(i)\), rappresentata da un multi-insieme; sia \(j\in A(i)\). Allora, \(S(i-t[j])\) e' un sottoproblema di \(S(i)\), la cui soluzione ottima e' data da \(A(i)-\{ j \}\).

\[DP[i]= \begin{cases} 0 & i=0 \\ min_{j\in R\ and\ t[j]

Complessità \(O(nR)\).

Proviamo ora a dimostrare una soluzione ingorda. Deve essere dimostrata per ogni scelta di monete, prendiamo come esempio \(t=[50, 10, 5, 1]\).

Sia \(x\) una qualunque soluzione ottima, quindi \(R=\sum_{i=1}^n x[i]t[i]\) e \(m=\sum_{i=1}^nx[i]\) ha valore minimo. Sappiamo che \(t[k]x[k] < t[k-1]\), altrimenti basterebbe sostituire un certo numero di monete di taglia \(t[k]\) con quelle del taglio \(t[k-1]\).

• \(t[2]x[2] = 10x[2] < t[1]=50 \rightarrow x[2] < 5\)
• \(t[3]x[3]=5x[3]
• \(t[4]x[4]=1x[4]

Sia \(m_k\) la somma delle monete di taglio inferiore a \(t[k]\): \(m_k = \sum_{i=k+1}^4x[i]t[i]\). Se dimostriamo che \(\forall k: m_k < t[k]\), allora la soluzione (ottima) e' proprio quella calcolata dall'algoritmo.

• \(m_4 = 0 < 1 = t[4]\)
• \(m_3 = x[4]*1 + m_4 \le 4*1+m_4 < 4+1 = 5 = t[3]\)
• \(m_2 = x[3]*5+m_3 \le 1*5+m_3 < 5+5 = 10 = t[2]\)
• \(m_1 = x[2]*10+m_2 \le 4*10+m_2 < 40+10 = 50 = t[1]\)

Supponiamo di avere un processore e \(n\) job da eseguire su di esso, ognuno caratterizzato da un tempo di esecuzione \(t[i]\) noto a priori. Trovare una sequenza di esecuzione che minimizzi il tempo di completamento medio definito come \(\frac{1}{n}\sum_{j=0}^n \sum_{i=1}^jt[A[i]]\) dove il vettore \(A[1..n]\) contiene una permutazione di \(\{ 1, ..., n \}\).

Teorema: Scelta greedy: esiste una soluzione ottima \(A\) in cui il job con minor tempo di fine \(m\) si trova in prima posizione (\(A[1]=m\)). Teorema: sottostruttura ottima: Sia \(A\) una soluzione ottima di un problema con \(n\) job, in cui il job con minor tempo di fine \(m\) si trova in prima posizione. La permutazione dei seguenti \(n-1\) job in \(A\) e' una soluzione ottima al sottoproblema in cui il job \(m\) non viene considerato.

Dimostrazione: Si consideri una permutazione ottima \(A\), sia \(m\) la posizione in \(A\) in cui si trova il job con minor tempo di fine. Si consideri una permutazione \(A'\) in cui il jon in posizione 1, \(m\) vengono scambiati. Il tempo di completamento medio di \(A'\) e' minore o uguale al tempo di completamento medio di \(A\). Poiche' \(A\) e; ottima, \(A'\) non puo' avere tempo di completamento minore e quindi anche \(A'\) e' ottima.

Dati un'intero positivo \(C\) che rappresenta la capacita' dello zaino, e \(n\) oggetti ognuno con un profitto \(p\) e un peso \(w\) in \(\mathbb{Z^+}\).

Zaino 0/1: Trovare un sottoinsieme \(S\) di \(\{ 1, ..., n \}\) di oggetti tale che il loro peso totale non superi la capacita' massima e il loro profitto totale sia massimo.

Zaino reale (o frazionario): e' possibile prendere frazioni di oggetti.

Scelta ingorda: Si possono ordinare gli oggetti per il rapporto profitto su peso e prenderli in questo ordine, se vi e' abbastanza capacita'.

In un codice a prefisso, nessun codice e' prefisso di un altro codice. Ad esempio con \(a\rightarrow 0,\ b\rightarrow 10,\ c\rightarrow 11\) possiamo codificare \(ababca\) con \(100100110\).

L'algoritmo di Huffman e' ottimo per costruire codici prefissi.

L'algoritmo di decodifica può essere visto come l'attraversamento di un albero binario, ed e' il seguente:

parti dalla radice
while file non e' finito do
  leggi un bit
  if bit e' zero then
    vai a sinistra
  else
    vai a destra
  if nodo foglia then
    stampa il carattere
    torna alla radice

Dato un file \(F\) composto da caratteri nell'alfabeto \(\sum\). Vogliamo minimizzare la lunghezza dei caratteri che compaiono più frequentemente.

Possiamo procedere nel seguente modo:

• costruiamo un nodo foglia per ogni carattere, etichettato con la propria frequenza
• rimuoviamo i due nodi con frequenza minore \(f_x, f_y\)
• creiamo un nodo con etichetta "-" e frequenza \(f_x+f_y\)
• colleghiamo i due nodi rimossi con il nuovo nodo
• aggiungiamo il nodo cosi' creato all'insieme
• si termina quanto resta un solo nodo sul primo livello
• al termine, si etichettano gli archi dell'albero con un bit \(0,1\).

Algoritmo:

Tree hiffman(int[] c, int[] f, int n)
  PriorityQueue Q = MinPriorityQueue()
  for i=1 to n do
    Q.insert(Tree(c[i], f[i]), f[i])
  for i=1 to n-1 do
    z1 = Q.deleteMin()
    z2 = Q.deleteMin()
    z = Tree(nil, z1.freq + z2.freq)
    z.left = z1
    z.right = z2
    Q.insert(z, z.freq)
  return Q.deleteMin()	

La dimostrazione non viene qui riportata. Intuitivamente, si assume di prendere i due caratteri con frequenza più bassa \(x\) e \(y\) e si dimostra che esiste un prefisso ottimo dove i due caratteri hanno la stessa profondità massima e i loro codici differiscono solo per l'ultimo bit. Per dimostrare ciò si suppone di avere un codice ottimo e, scambiando i due caratteri, abbiamo ancora una soluzione ottima.

Dato un grafo pesato, determinare come interconnettere tutti i suoi nodi minimizzando il costo del peso associato ai suoi archi.

Set kruskal(Edge[] A, int n, int m)
  Set T = Set()
  Mfset M = Mfset(n)
  % ordina A per peso
  int count = 0
  int i=1
  % Termina quando l'albero ha n-1 archi
  % o non ci sono piu' archi
  while count < n-1 and i <= m do
    if M.find(A[i].i) != M.find(A[i].v) then
      M.merge(A[i].w, A[i].v)
      T.insert(A[i])
      count = count + 1
    i = i + 1
  return T