Newsgroup: it.scienza.informatica
Titolo: [LUNGO] Problema dello zaino discreto con un vincolo in piu'

Salve a tutti.
Come da titolo del post, per la preparazione ad un esame scritto ho 
incontrato una traccia che, per la soluzione del problema, presenta le 
caratteristiche di approccio dello zaino [0,1] ma con l'aggiunta di un 
"vincolo".
Premetto che l'esame non è di Ricerca Operativa (quindi niente 
programmazione lineare, intera, e cose simili...) ma di Algoritmi e 
Strutture Dati II.
La traccia che riporto richiede espressamente una soluzione che fa uso 
della tecnica di Programmazione Dinamica.
Ecco il testo:
"Il presidente di una squadra di calcio deve acquistare dei giocatori da 
un insieme di N. A ciascun giocatore i-esimo sono associate una 
valutazione della bravura, detta val(i), ed un prezzo di mercato, detto 
prezzo(i).
Il presidente desidera acquistare esattamente K giocatori (con K <= N) 
in modo da non spendere più di V euro e massimizzare al tempo stesso il 
tasso complessivo di bravura (inteso come somma dei tassi di bravura).
Si progetti quindi un algoritmo di programmazione dinamica che risolva 
il problema."
A prima vista sembra di una semplicità disarmante:
- capacità dello "zaino": V euro di spesa massima
- insieme degli "oggetti": N giocatori
- valore dell'"oggetto" i-esimo: val(i)
- "peso" dell'"oggetto" i-esimo: prezzo(i)
- vincolo: gli "oggetti" (i giocatori) devono essere esattamente K.
Bene, quello che mi disorienta è proprio l'"esattamente K".
Mi spiego.
In "condizioni normali", quando lo "zaino" è un classico [0,1], 
considerando l'approccio tipico della programmazione dinamica, la prima 
cosa che si fa è cercare se esiste (e poi dimostrare) la caratteristica 
della sottostruttura (ottima)...
Quindi così:
Sia I={ e1, e2, … , en } l'insieme degli oggetti.
Sia P il peso totale che può reggere lo zaino.
Sia V(i) il valore dell'i-simo elemento.
Sia W(i) il peso dell'i-simo elemento.
Voglio trovare una configurazione X tale che X(i)=0 oppure X(i)=1 a 
seconda che ei è, rispettivamente, escluso o incluso nella 
configurazione per cui valgono le seguenti relazioni:
SUM [i=1...n] (X(i)*W(i)) <=P
e
SUM [i=1...n] (X(i)*V(i)) = Max valore
e al PASSO 1 della programmazione dinamica (struttura di una soluzione 
ottima) farei:
Sia X una soluzione ottima.
- Se X(n) = 0 allora i restanti n-1 elementi nella configurazione X 
rappresentano una soluzione ottima per uno zaino di capacità P.
Infatti, se così non fosse, potrei trovare una configurazione degli n-1 
elementi per uno zaino di capacità P tale che:
SUM [i=1...n-1] (X(i)*W(i)) <=P
e
SUM [i=1...n-1] (X(i)*V(i)) = Max valore
e, sostituendo tale configurazione in X, otterrei una soluzione 
migliore. Ma ciò contrasta con l'ipotesi che X è una soluzione ottima.
-Se X(n) = 1 allora i restanti n-1 elementi nella configurazione X 
rappresentano una soluzione ottima per uno zaino di capacità P �€" W(n).
Infatti, se così non fosse (etc. etc)
Ma in questo caso in cui ho quel "esattamente K" come faccio per dire 
quello che ho detto al PASSO 1 ?
Inoltre, normalmente al PASSO 2 (def. ricorsiva del valore di una sol. 
ottima) direi:
Definisco M[i, j] una funzione che rappresenta il valore massimo degli 
oggetti scelti nel sottoinsieme {e1, e2, … , ei } e caricabili in uno 
zaino di capacità j (dove per capacità si intende il peso massimo 
trasportabile).
CASO BASE:
- M[i, 0] = 0 per ogni i = 0 … n
(con questo intendo dire che se ho uno zaino di
capacità nulla, la funzione M ritorna 0 come
valore massimo, qualsiasi sia il numero degli
oggetti considerati)
- M[0, j] = 0 per ogni j = 0 … P
(con questo intendo dire che qualunque sia la
capacità dello zaino e l’insieme degli oggetti è
vuoto, la funzione M ritorna 0 come valore
massimo)
PASSO INDUTTIVO:
M[i, j] =
- M[i-1, j] se j < W(i)
- MAX { M[i-1, j] , M[ i-1, j �€" W(i)] + V(i) } se j => W(i)
Ma nel caso in cui devo considerare  i K giocatori? Che faccio? così? :
M[i, j, k] è una funzione che rappresenta il valore massimo dei 
giocatori scelti in 1...N e che si possono inserire in uno "zaino" di 
capacità j, nel numero esatto di k (???)
M[i, 0 , k] = 0 , per ogni i=0...N (quando ho uno zaino di "capacità" nulla)
M[0, j, k]=0 , per ogni j=0...V (quando l'insieme da cui scegliere i 
giocatori è vuoto) (???)
M[i,j,k]= M[i-1, j, k-1] , se j < prezzo(i);
M[i,j,k]= max { M[i-1, j, k-1], M[i-1, j-prezzo(i), k] + val(i) } , se j 
=>prezzo(i)
  ---
Va da se che è chiaro che la matrice che sarà usata per arrivare alla 
soluzione è tridimensionale, però non riesco proprio ad entrare 
nell'ottica di idee che mi porta a gestire agevolmente questo vincolo K 
in più.
Girando tra i vecchi post su questo ed altri NG ho trovato una cosuccia 
in un post del 2003 in cui la traccia è simile.
[CIT]: Vendicator dice:
"Variabili: x_i, binarie, valgono 1 se il calciatore a_i è stato 
selezionato, 0 altrimenti.
Funzione obiettivo da massimizzare: sommasu_i(d_i * x_i)
Vincoli:
sommasu_i(c_i * x_i) <= K       (Vincolo sul budget)
sommasu_i(x_i) = k              (Vincolo sul numero di calciatori,
l'uguale può eventualmente essere trasformato in
minore o uguale).
[/CIT]
Ma come lo uso sto vincolo? :|
Qualche animo gentile mi vuole/può aiutare a colmare questa mia lacuna?
---------------
Alexandros


Possibile che in 5 mesi e mezzo (circa) nessuno abbia ancora risposto al 
mio post?
Bah...


Scusa, non ho risposto perche' non sono esperto di dynamic programming, 
comunque a me verrebbe da fare cosi`:
Uso un array A[i] che rappresenta per ogni i la soluzione ottima che 
riesco ad ottenere con peso <=i (e con al massimo k elementi). Sia 
Val(A[i]) il valore della soluzione (quindi in A[i] salvo la soluzione 
stessa: e` un array che dice chi viene preso e chi no, mentre Val(A[i]) 
dice quanto vale questa soluzione).
Se C e` il costo totale, evidentemente la soluzione del tuo problema e` 
A[C].
A[0]= non prendo nessuno e Val(A[0])=0.
Ora, se devi calcolare A[i] come fai?
Se sai gia` tutti i valori degli A[j] per j<i, puoi dire:
Per ogni elemento b
- Considero l'elemento b: forse posso inserirlo. Guardo la soluzione 
A[j-c(b)].
    - Se b e` gia` nella soluzione, non posso aggiungerlo
    - Se b si puo` aggiungere, cioe` se ho al massimo k-1 elementi, 
aggiungilo e metti questa soluzione temporaneamente in A[j]
    - Altrimenti, se ho gia` k elementi, devo provare a scambiare uno 
degli elementi che ho nella soluzione A[j-c(b)] con b. Se ne trovo uno 
feasible (cioe` che ci sta nello zaino) e che migliora la soluzione che 
ho attualmente in A[j], mi salvo la nuova soluzione in A[j].
Spero che sia comprensibile, scusa se c'e` qualcosa che non torna, ma di 
dynamic programming non so moltissimo.
Ciao,
Arcangelo
--
il Decreto Legge 112 consente alle Universita` pubbliche di diventare 
fondazioni private, cosi` poi potranno aumentare le tasse universitarie.
http://cga.di.uniroma1.it/