Newsgroup: it.scienza.informatica
Titolo: Programmazione dinamica ...

Salve,
ecco l'ennesima domana sulla programazione dinamica.
Di solito io ho qualche difficolta' nell'individuare la sottostruttura
ottima di un dato problema, potreste consigliarmi qualche "approccio
metodologico" per individuare tale sottostruttura ? (un trucco del
mestiere, insomma).
Mi rendo conto che lo studio e ... l'ingegno (o la fantasia ?) devo
metterceli io, vi chiedo solo un sugerimento :)
E propongo un esempio:
--- Inizio esempio ---
Fantacalcio. Il signor Sensotti è il presidente di una grossa squadra
di calcio che ha avuto mandato di formare una squadra in grado di
vincere la Champions League del prossimo anno. La società gli ha
messo a disposizione un badget di K fantamiliardi.
Sensotti deve scegliere k calciatori tra una lista
di n calciatori (a1, a2, ..., an) disponibili,
dove ogni calciatore ai ha una quotazione c_i
ed un coefficiente di bravura d_i.
Progettare un algoritmo di programmazione dinamica che aiuti
il presidente Sensotti a selezionare la squadra migliore possibile
con il budget a disposizione. 
Supponendo che ad ogni calciatore sia associato un codice r_i che
identifica un ruolo e che i ruoli possibile sono m, modificare
l'algoritmo in modo che la squadra selezionata sia la migliore
possibile tra tutte quelle che hanno almeno n_j calciatori di
ruolo j, per j = 1, 2, ..., m.
--- Fine Esempio ---
Beh, qui il problema credo sia riconducibile a quello dello zaino 0-1,
ma il fatto che si debbano scegliere esattamente ( o almeno) k
calciatori mi disorienta... la soluzione
sara' nello'orine di O(n*k*K) ?? il vincolo dei k calciatori aggiunge
una ulteriore dimensione al problema ?
Grazie infinite per la pazienza,
  RN.

 una ulteriore dimensione al problema ?
Non so proprio rispondere. Sorry :-)
-- 
Andrea Bergia - studente              Linux Registered User #281550

 d_i / c_i. A questo punto č uguale allo zaino.
Non capisco a cosa possa servire questa formula.
Un problema di zaino č:
max(sommasu_i(valore_i * x_i))
sommasu_i(peso_i * x_i) <= P

 una ulteriore dimensione al problema ?
Il problema non è riconducibile ad uno di zaino, poichè un problema di zaino
ha un solo vincolo, mentre questo ne ha 2 + m.
La dimensione del problema dipende dal numero delle variabili e dai vincoli.
Le soluzioni possibili sono 2^n, e solo un sottoinsieme di queste è
ammissibile.
Ciao.

 --- Fine Esempio ---
Per quanto riguarda la prima metà, io la risolverei così, anche se non sono
sicuro dell'esattezza (è tardi e sono stanco :) :
Hai una matrice di K righe e k colonne, per cui all'elemento (I, J) hai I
fantamiliardi per comprare J giocatori. Allora per ogni giocatore a tra
quelli che non hai ancora messo in quella cella puoi propagare la soluzione
alla cella (I+c_a, J+1), cioè sostituisci il valore se è minore di quello
finora trovato, come ogni normale dinamica.
Trovare ad ogni cella i giocatori che hai già messo costa O(k), per cui la
complessità dell'algoritmo è (nKk^2).
Il punto su cui ho dubbi è il fatto che ad ogni posizione ti precludi la
possibilità di mettere giocatori che hai già messo, ma visto che l'ordine
dei giocatori è arbitrario, non dovresti perdere soluzioni ottime, quindi
l'algoritmo dovrebbe essere ottimo.
Per quanto riguarda i ruoli:
Secondo me va fatta una matrice a j+1 dimensioni, dove una dimensione è K, e
le altre sono ogni n_j. A questo punto propaghi come sopra. Una volta che
hai ottenuto una squadra ottima per ESATTAMENTE n_j giocatori di ruolo j, ti
riconduci al problema precedente per sfruttare i fantamiliardi rimasti.
La complessità ad occhio dovrebbe essere O(nK(n_j)^(j+1)) o qualcosa di
simile. E' tantino, ma se i giocatori sono 11, è accettabile (mi preoccupo
di più del costo massimo, ma le dinamiche di questo tipo sono polinomiali al
valore, e quindi...):)
Spero di non aver detto minchiate :)
Ciao,
Giuseppe

 finora trovato, come ogni normale dinamica.
Ripensandoci forse ti conviene fare il contrario, cioč per ogni cella ancora
da calcolare vai a vedere la cella (I - c_a, J-1) e provi ad aggiungere il
giocatore a (per ogni a possibile, cioč non scelto sinora), perň il concetto
č lo stesso.

Sinceramente non ho capito il tuo algoritmo.
Comunque, il valore di K a mio avviso dovrebbe essere un numero reale,
quindi come fai ad utilizzarlo come dimensione di una matrice?
Anche le quotazioni dei calciatori sono numeri reali.
A mio avviso il problema è un classico problema di programmazione lineare
intera con 2 + m vincoli.
Quindi andrebbe risolto con un normale simplesso + branch and bound +
(eventualmente) cover cuts.
Ciao.

 
Beh il problema e' posto come risolvibile con tecniche di programmazione
dinamica per un esame di Algoritmi e strutture dati (e non di Ricerca
Operativa).
Ciao,
RN.

 (eventualmente) cover cuts.
Secondo me K è naturale... quando facevo il fantacalcio le quotazioni erano
tutte intere...
Ciao,
Giuseppe

Scusa ma non avevo mai fatto programmazione dinamica.
Questi problemi ero solito risolverli con gli algoritmi della ricerca
operativa.
Non so dei due metodi quale sia il migliore, cmq se ti interessa ti posso
dare il sito del mio prof.
www.unipa.it/~pesenti
Ciao.

 Spero di non aver detto minchiate :)
Ciao Ottavio,
io a occhio (ma non ci ho pensato niente) direi che e' giusto, quindi se ho
capito bene metterei tutti i giocatori in un ordine arbitrario, e farei una
tabella di n*K*n_1*n_2*...*n_n, dove l'elemento table[n][k][n1]...[nn]
contiene la miglior squadra fatta usando k fantamiliardi, n1 giocatori di
ruolo 1, n2 di ruolo 2 e cosi' via ed utilizzando solo i giocatori 0...n-1
(o a chi non piace il C i giocatori 1...n) nell'ordine arbitrario in cui li
hai messi. La funzione ricorsiva dovrebbe essere del tipo (non la ho
provata, la butto li):
int best_team(int n,int k,int n1,int n2)
{
migliore fra:
    best_team(n-1,k,n1,n2)        // Se la soluzione usa il giocatore n
    best_team(n-1,k-c[n],n1-isrole(1,n),n2-isrole(2,n))+d[n] // se non lo
usa, dove isrole(r,n) torna 1 se il giocatore n ha ruolo r, senno' 0
// poi tutti i casi speciali, cioe' se siamo arrivati ad n1 minore di n_1 o
n2 di n_2, ecc.
}
Non dovrebbe essere troppo difficile da scrivere, anzi, direi che ti
conviene usare un approccio top-down, visto che ti salti molte
configurazioni impossibili, rendendolo ancora piu' facile e partendo
direttamente dalla ricorsione, rendendolo O(nK*  (sigma(j=0,m-1) n_j))
anziche theta di quella roba li', cioe' il lower bound puo' essere molto
piu' basso.
Bene, adesso non vorrei aver sparato la cavolata del secolo, ma non ho
voglia di vedere se e' giusto.
ciao

 direttamente dalla ricorsione, rendendolo O(nK*  (sigma(j=0,m-1) n_j))
pardon, intendevo PI(j=0,m-1) n_j
