Newsgroup: it.comp.lang.c++
Titolo: Programmazione dinamica... Problema:

Problema:
Data una lista di tutti i calciatori del campionato con rispettivi ruolo,
costo e bravura, un budget, un tipo di formazione (ovvero quanti difensori,
quanti attaccanti ecc.) implementare un algoritmo che formi la migliore
squadra possibile (dove A è migliore di B se la somma dei valori di bravura
dei giocatori di A è superiore a quella dei valori di bravura dei giocatori
di B) che rispetti la formazione indicata e il cui costo sia minore o uguale
al badget specificato.
La questione ricorda molto da vicino il famoso problema dello zaino, ma
stavolta bisogna tener conto delle quantità di oggetti inseriti nello zaino
(calciatori nella squadra) a seconda del tipo di oggetto (ruolo del
giocatore). Un bel casino, insomma... qualche idea?
_
Francesco "SiSkO" Napolitano

 giocatore). Un bel casino, insomma... qualche idea?
I vincoli posti ti semplificano la vita, anche se non permettono
una prova esaustiva.
Supponiamo che le squadre del campionato siano 16 e la formazione
richiesta sia, ad esempio, 1 portiere, 3 difensori, 4 centrocampisti,
3 attaccanti.  Le squadre avranno in tutto, ad es, 32 portieri, 96
difensori, 128 centrocampisti, 96 attaccanti.
Il numero di squadre che si possono formare, detto C(n,m) il
numero di combinazioni di n oggetti m alla volta (n!/m!(n-m)!):
C(32,1) * C(96,3) * C(128, 4) * C(96,3).
C(32,1) e` 32.
C(96,3) e` 96*95*94/(3*2*1) = 142,880
C(128,4) e` 10,668,000
In breve, puoi dunque agevolmente calcolare e memorizzare i
32 possibili portieri, le 142,880 possibili difese, i
142,880 possibili attacchi, e i 10 milioni e rotti di
"centrocampi", ciascuno dei 4 ruoli con un costo e una
efficienza; al peggio stiamo parlando (per i centrocampi)
di 10 milioni di "celle" di 2 numeri ciascuna, 80 megabyte
al peggio, su di un PC moderno con memoria virtuale te li
puoi permettere.
Nota che, piu` frammentato il set dei ruoli, meglio sei
messo.  Qui, e` solo il "centrocampo" a dare problemi.
Puoi poi ridurre per ciascun ruolo i numeri eliminando
le combinazioni "dominate" (piu` costose e meno
efficienti di altre).  Se la "bravura" e` un numero
intero e piccolo, ad esempio un voto da 1 a 100, sei
sicuro di trovare non piu` di 400 centrocampi
non-dominati: il meno costoso di bravura totale 400,
il meno costoso di bravura totale 399, e cosi` via.
In questo caso torna la voglia di andare poi per
enumerazione esaustiva.  Un max di 30 possibilita`
per il ruolo portiere, 300 ciascuna per attacco e
difesa, 400 per il centrocampo, sono in tutto
pochi miliardi.  Ma questo e` ancora un sostanziale
consumo di CPU, quindi, meglio aspettare.
Potresti invece considerare le 300*400 accoppiate
centrocampo/attacco; al massimo 700 saranno non
dominate, e cosi` via.
Se la dominanza in senso stretto non e` possibile
(le 'bravure' sono numeri in una gamma molto vasta)
puoi provare un'aritmetica d'intervallo.  Se ad
esempio la bravura e` un numero REALE fra 0 e 100,
rappresenta ogni numero reale con la coppia di
interi subito inferiore e subito superiore; anche
cosi` puoi certamente ottenere molte combinazioni
dominate e ridurre i 10 milioni di possibili
centrocampi, se non a 400 al massimo, a poche
migliaia.  A un certo punto puoi rinunciare a una
soluzione esatta perche` in realta` non c'e` una
misura infinitamente precisa di 'bravura', quindi
le approssimazioni che ottieni rappresentano invece
la bravura con piccoli interi non peggiorano la
qualita` della soluzione.
Alex

[PROPOSTE DI SOLUZIONE]
Le tue soluzioni sono interessanti, ma, come scritto in topic, ho bisogno di
risolvere questo problema mediante programmazione dinamica, non posso in
nessun caso generare una per una tutte le possibili combinazioni.
Ti ringrazio molto, spero tu abbia anche altri suggerimenti.
Ciao,
_
Francesco "SiSkO" Napolitano

 nessun caso generare una per una tutte le possibili combinazioni.
Se l'algoritmo che devi usare e` fra le specifiche, usalo.  Se no, usa
il miglior algoritmo che riesci a escogitare, e mi sembra che quelli
che suggerivo non fossero male.  Non sono esaustivi perche` il calcolo
sarebbe eccessivo: sono basati sulla semplificazione data dalla divisione
della squadra in ruoli, trasformando il problema di dimensione 11 in
N sottoproblemi, uno per ruolo, di dimensioni n1, n2, ... nX con somma
11.  Nella espressione 'programmazione dinamica' non vi e` nessuna
implicazione che si DEBBANO considerare potenziali soluzioni che si
possono agevolmente dimostrare essere dominate da altre, dopo tutto:-).
Alex

Io pensavo fosse quella che si fa senza mai dichiarare variabili
statiche o automatiche... Anche Georges Perec, autore de "La vita
istruzioni per l'uso", scrisse un romanzo senza la lettera "e"!
Ciao,
Nicola

 Scusa sai, ma non ho potuto resistere...
Forse meno divertenti, ma potenzialmente piu` utili:
http://mail.informs.org/classes/dynamic/dynamic.html
http://www.ms.unimelb.edu.au/~moshe/dp/dp.html
http://www.catalase.com/frames/dprog.htm
http://pass.maths.org/issue3/dynamic/
http://envy.cs.umass.edu/~rich/book/4/node1.html
E` un tema sul quale si trovano molti "falsi successi"
in rete (le parole "dynamic programming" usate per
descrivere tutt'altre cose piuttosto che non il concetto
matematico di "programmazione dinamica") e quindi una
volta tanto non basta saper usare bene un motore di
ricerca in Web.
Alex