kily2001
04-06-2009, 12:30
ciao a tutti, dovrei eseguire questo esercizio con la programmazione dinamica:
Si consideri una sequenza di interi X. La cancellazione da X di
un certo numero di elementi determina una sottosequenza. Una k-sottosequenza di X è una
sottosequenza di X in cui compaiono al più k elementi consecutivi di X.
Data una sequenza X di n interi ed un intero k, con k <= n vogliamo trovare una k-sottosequenza
di X la somma dei cui elementi sia massima.
Ad esempio, per X = (9, 8, 1, 9, 2, 9, 8, 2, 1, 8, 8, 1) e k = 3 la 3-sottosequenza a somma massima è
(9, 8, 9, 9, 8, 8, 8, 1) e vale 60.
Visto che il costo deve essere O(k*n) avevo pensato di usare una matrice T di grandezza k*n, dove nel generico T[i,j] trovo il massimo valore per la j-sottosequenza di X1...Xi (ad esempio considerando i=4 e j=2 avrò la 2-sottosequenza 9-9-9 che vale 27).
Qualcuno mi aiuta ad impostare la ricorrenza?
Grazie mille
Si consideri una sequenza di interi X. La cancellazione da X di
un certo numero di elementi determina una sottosequenza. Una k-sottosequenza di X è una
sottosequenza di X in cui compaiono al più k elementi consecutivi di X.
Data una sequenza X di n interi ed un intero k, con k <= n vogliamo trovare una k-sottosequenza
di X la somma dei cui elementi sia massima.
Ad esempio, per X = (9, 8, 1, 9, 2, 9, 8, 2, 1, 8, 8, 1) e k = 3 la 3-sottosequenza a somma massima è
(9, 8, 9, 9, 8, 8, 8, 1) e vale 60.
Visto che il costo deve essere O(k*n) avevo pensato di usare una matrice T di grandezza k*n, dove nel generico T[i,j] trovo il massimo valore per la j-sottosequenza di X1...Xi (ad esempio considerando i=4 e j=2 avrò la 2-sottosequenza 9-9-9 che vale 27).
Qualcuno mi aiuta ad impostare la ricorrenza?
Grazie mille