Esercizio algoritmo programmazione dinamica
salve dovrei svolgere il seg. esercizio
ho una tabella non completa corrispondente all'applicazione di un algoritmo di prog. dinamica
§Gli elementi della tabella che mi fornisce l'esercizio sono i seguenti
tutta la riga 0 contiene elementi tutti nulli e poi
a1,0=0 a1,1= 0 a1,3=0 a1,4= 6
a2,0=0 a2,3 = 3 a2,4 = 6
a3,0= 0 a 3,2 =4 a3,3= 4 a3,4 = 9
a4,0 = 0 a4,2 = 4 a4,3 = 5
a 5,0 = 0 a5,1=4 a5,2= 4 a5,3= 7
a6,0 = 0 a6,1= 4 a6,2=7 a6,3=8
dove sulle righe è riportato il peso e sulle colonne il n. di oggetti
Mi chiede di completare la tabella di scrivere di che tipo di problema si tratta, di formularlo e calcolare la soluzione ottima.
so che occorre applicare la funzione ricorsiva f(r, λ) = max ( f(r-1,λ), c(r) + f(r-1,λ-a(r))
si legga c con pedice r ed a con pedice r
si tratta di un problema di knapsack binario con 4 oggetti r= 1....4 e peso
max b= 6 infatti λ= 1....6
max c1x1+c2x2+c3x3+c4x4
s.t. a1x1+a2x2+a3x3+a4x4<=6
0<=xi<=1, e intere
Quindi abbiamo 4 variabili da determinare.
Ora se ad sempio sfrutto il dato f(1,1) = 0 avro
f(1,1) = max (f(0,1), c(1)+f(0, 1- a(1)) =0
f(1,1) = max (0,c(1)+ f(0, 1- a(1))
ora f(0, 1- a(1) ) puo essere >, < o = 0..... come faccio a determinare
i coefficienti di costo c1 c2 c3 c4 e i pesi a1 a2 a3 a4? per poter
completare la tabella?
ho una tabella non completa corrispondente all'applicazione di un algoritmo di prog. dinamica
§Gli elementi della tabella che mi fornisce l'esercizio sono i seguenti
tutta la riga 0 contiene elementi tutti nulli e poi
a1,0=0 a1,1= 0 a1,3=0 a1,4= 6
a2,0=0 a2,3 = 3 a2,4 = 6
a3,0= 0 a 3,2 =4 a3,3= 4 a3,4 = 9
a4,0 = 0 a4,2 = 4 a4,3 = 5
a 5,0 = 0 a5,1=4 a5,2= 4 a5,3= 7
a6,0 = 0 a6,1= 4 a6,2=7 a6,3=8
dove sulle righe è riportato il peso e sulle colonne il n. di oggetti
Mi chiede di completare la tabella di scrivere di che tipo di problema si tratta, di formularlo e calcolare la soluzione ottima.
so che occorre applicare la funzione ricorsiva f(r, λ) = max ( f(r-1,λ), c(r) + f(r-1,λ-a(r))
si legga c con pedice r ed a con pedice r
si tratta di un problema di knapsack binario con 4 oggetti r= 1....4 e peso
max b= 6 infatti λ= 1....6
max c1x1+c2x2+c3x3+c4x4
s.t. a1x1+a2x2+a3x3+a4x4<=6
0<=xi<=1, e intere
Quindi abbiamo 4 variabili da determinare.
Ora se ad sempio sfrutto il dato f(1,1) = 0 avro
f(1,1) = max (f(0,1), c(1)+f(0, 1- a(1)) =0
f(1,1) = max (0,c(1)+ f(0, 1- a(1))
ora f(0, 1- a(1) ) puo essere >, < o = 0..... come faccio a determinare
i coefficienti di costo c1 c2 c3 c4 e i pesi a1 a2 a3 a4? per poter
completare la tabella?
Risposte
la tabella è questa
