Esercizio algoritmo programmazione dinamica

corsara73
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?

Risposte
corsara73
la tabella è questa

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.