ASD Lab 8
Alessio Guerrieri
UniTN
5-12-2014
Alessio Guerrieri (UniTN)
ASD Lab 8
5-12-2014
1 / 13
C ALENDARIO (UPDATE)
Mar 9 (14-16): presentazione progetto + lezione Montresor
Mer 10 (11-13): LABORATORIO IN AULA PC (lavoro al progetto)
Ven 12: NESSUNA LEZIONE
Mer 17 (11-13): LABORATORIO IN AULA PC (lavoro al progetto)
Ven 19 (11-13): seconda provetta
Ven 19 (20): scadenza secondo progetto
S ECONDO PROGETTO
Programmazione dinamica, da 1 a 3 punti bonus, assumo stessi
gruppi.
Alessio Guerrieri (UniTN)
ASD Lab 8
5-12-2014
2 / 13
Z AINO
Funzione di ricorrenza (v [i]:valore dell’iesimo elemento, p[i]:peso
dell’iesimo elemento)
− inf
0
(
S(C, i) =
v [i] + S(C − p[i], i + 1)
Max S(C, i + 1)
Alessio Guerrieri (UniTN)
ASD Lab 8
if C < 0
if i == N
if i < N
5-12-2014
3 / 13
Z AINO RICORSIVO
1
2
3
4
5
6
7
8
9
int ric(int c,int i){
if(c<0)
return -100000000;
if(i==N)
return 0;
int p=elements[i].first;
int v=elements[i].second;
return max(v+ric(c-p,i+1),ric(c,i+1));
}
Alessio Guerrieri (UniTN)
ASD Lab 8
5-12-2014
4 / 13
Z AINO MEMOIZATION
1
2
3
4
5
6
7
8
9
10
11
12
int ric(int c,int i){
if(c<0)
return -100000000;
if(i==N)
return 0;
if(sav[c][i]==-1){
int p=elements[i].first;
int v=elements[i].second;
sav[c][i]= max(v+ric(c-p,i+1),ric(c,i+1));
}
return sav[c][i];
}
Alessio Guerrieri (UniTN)
ASD Lab 8
5-12-2014
5 / 13
Z AINO ITERATIVO
Il calcolo di S(c,i) dipende dagli S(c’,i+1).
Calcoliamo prima tutti gli S( ,N-1), poi tutti gli S( ,N-2)...
1
2
3
4
5
6
7
8
9
10
11
for(int i=N-1;i>=0;i--){
int p=elements[i].first;
int v=elements[i].second;
for(int c=0;c<=C;c++){
if(elements[i].first<=c)
sav[c][i]=max(sav[c][i+1],v+sav[c-p][i+1]);
else
sav[c][i]=sav[c][i+1];
}
}
}
Alessio Guerrieri (UniTN)
ASD Lab 8
5-12-2014
6 / 13
Z AINO ITERATIVO EFFICENTE
Una volta calcolati tutti gli S( ,i), gli S( ,i+1) non ci servono piu.
Utilizziamo un array C*2
1
2
3
4
5
6
7
8
9
10
11
for(int i=N-1;i>=0;i--){
int p=elements[i].first;
int v=elements[i].second;
int cur=i%2; int next=(i+1)%2;
for(int c=0;c<=C;c++){
if(elements[i].first<=c)
sav[c][cur]=max(sav[c][next],v+sav[c-p][next]);
else
sav[c][cur]=sav[c][next];
}
}
Alessio Guerrieri (UniTN)
ASD Lab 8
5-12-2014
7 / 13
S OTTOSEQUENZA CRESCENTE
Data una sequenza di interi scegliere un sottoinsieme della sequenza
in modo che:
gli elementi del sottoinsieme, messi nell’ordine in cui si trovavano
nella sequenza originaria, formino una sequenza crescente
il sottoinsieme abbia somma massima
S OTTOPROBLEMA
S(i) = somma della sottosequenza crescente di somma massima a
partire dall’elemento i
NON FUNZIONA! Per scegliere ottimamente, abbiamo bisogno di
sapere l’ultimo elemento scelto
Alessio Guerrieri (UniTN)
ASD Lab 8
5-12-2014
8 / 13
S OTTOSEQUENZA CRESCENTE
S OTTOPROBLEMA
S[i, j]= soluzione per il sottoarray [i..N − 1] avendo scelto per ultimo
l’elemento j
if i == n
0,
S[i, j] = S[i + 1, j],
if A[i] < A[j]
max(S[i + 1, j], S[i + 1, i] + A[i]) if A[i] ≥ A[j]
Alessio Guerrieri (UniTN)
ASD Lab 8
5-12-2014
9 / 13
S OTTOSEQUENZA CRESCENTE
S OTTOPROBLEMA ALTERNATIVO
S[i] =soluzione da i in poi avendo scelto l’elemento i
S[i] = A[i] + maxj:(j>i , A[j]≥A[i]) (S[j])
La soluzione del problema e´ uguale a max(S)
Alessio Guerrieri (UniTN)
ASD Lab 8
5-12-2014
10 / 13
E SPRESSIONE
S OTTOPROBLEMA
S[i, j] = insieme dei valori ottenibili usando il sottoarray A[i...j]
function C OMPUTE S(i,j)
Res = ∅
if i = j then
Res = {A[i]}
else if i + 1 = j then
Res = {A[i] + A[j], A[i] ∗ A[j]}
else
for k = i + 1 to j do
for all l ∈ S[i, k − 1] do
for all r ∈ S[k, S
j] do
Res = Res {l + r , l ∗ r }
end for
end for
end for
end if
return Res
end function
Alessio Guerrieri (UniTN)
ASD Lab 8
O(N 3 × M 2 )
5-12-2014
11 / 13
P ROBLEMI
S OTTOSEQUENZA COMUNE MASSIMALE
Date due stringhe di caratteri alfanumerici, calcolare una
sottosequenza comune massimale (secondo la definizione delle slides
di Montresor). Stamparne la lunghezza
Lettura di una stringa (libreria string):
1
2
string s;
in>>s;
Ottenere dimensione stringa e valore per un singolo carattere
1
2
int dim=s.size();
char c=s[2];
Alessio Guerrieri (UniTN)
ASD Lab 8
5-12-2014
12 / 13
P ROBLEMI
D EFINIZIONE : N ODE -C OVER
Un insieme S ⊆ V di nodi e´ un Node-Cover se ogni arco nel
grafo/albero ha almeno uno dei due nodi in S
M IN C OVER SU ALBERO
Dato un albero, trovare la dimensione del Node-Cover di dimensione
minima.
M IN COVER SU ALBERO PESATO
Dato un albero con pesi su i nodi, trovare il Node-Cover di peso
minimo e stamparne il peso.
Alessio Guerrieri (UniTN)
ASD Lab 8
5-12-2014
13 / 13
© Copyright 2024 ExpyDoc
