Input: Un insieme \( \{1,\ldots,n\} \) di \(n\) giocatori dove ciascun giocatore \(i\) è caratterizzato dai seguenti dati
1) \( s_i \geq 0 \) - un intero che descrive le sue skills
2) \( p_i \geq 0 \) - un intero che descrive il prezzo per acquistare \(i\).
In più è dato un intero non negativo \(T\) che è la somma richiesta di skills dei nuovi giocatori.
Output: Il costo più piccolo \(C\) tale che esiste un sottoinsieme \(P \subseteq \{1,\ldots,n \} \) di giocatori che soddisfano
\[ \sum_{i \in P} p_i = C \]
e
\[ \sum_{i \in P} s_i \geq T \]
a) Sia \( c[i,t] \) il costo minimale di una soluzione per l'istance (istanza?) che consiste nei primi \(i\) giocatori \( \{1,\ldots,i \} \) e che richiede come skills totale \(t\). In altre parole \( c[i,t] \) è il costo più piccolo tale che \(P \subseteq \{1,\ldots,i \} \) di giocatori che soddisfano
\[ \sum_{j \in P} p_j = c[i,t]\]
e
\[ \sum_{j \in P} s_j \geq t
\]
completa la relazione di ricorrenza per \( c[i,t] \) che può essere usata per la programmazione dinamica.
b) Scrivi un algoritmo in pseudocodice usando l'approccio bottom-up.
a) La mia relazione è questa
\[ c[i,t] =\left\{\begin{matrix}
\infty & \text{if} & t>0 \text{ and } i=0 \\
0 & \text{if} & t=0 \\
\min\{ p_i + c[i-1,t-s_i] , c[i-1,t] \} & &
\end{matrix}\right.
\]
Ora ho difficoltà ad implementare l'algoritmo
Sia \( p \) la lista dei prezzi e \(s\) la lista delle skills in ordine. Sia Team un sottoinsieme dei giocatori
Mourinho(p,s,T)
- Codice:
C and empty array of array of dimension nT
for i = 0 to n
c[i,0] = 0
end
for t = 1 to T
c[0,t] = infty
end
for t=1 to T
for i= 1 to n
c[i,t] <- infty
if t- s[i] >= 0
if c[i-1, t] >= c[i-1,t-s[i] ] + p[i]
c[i,t] <- p[i] + c[i-1,t-s[i] ]
else
c[i,t] <- c[i-1,t]
else if t- s[i] < 0
if c[i-1, t] >= c[i-1,0] + p[i]
c[i,t] <- p[i] + c[i-1,0 ]
else
c[i,t] <- c[i-1,t]
end
end
return c[n,T]