[Teoria] Bottom-up

[Studente Anonimo]

In questo problema aiuterai Mourinho a rimettere il Chelsea di nuovo in pista. In particolare devi fare un algoritmo per comprare l'insieme di giocatori meno caro che formino un "buon team": la somma delle loro abilità dovrebbe avere una soglia di almeno \(T\). Nel nostro modello astratto assumiamo che ciascun giocatore è caratterizzato da un intero che rappresenta le sue abilità e da un prezzo del cartellino. La definizione formale del problema è la seguente

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)

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]

[Quinzio]

Qui sotto c'e' il codice che dovrebbe fare quello che hai implementato.
In questi esercizi, per avere vita lunga e preservare la salute mentale, ti consiglio di usare un linguaggio di programmazione reale, tipo il C, che poi non e' molto diverso da uno pseudo codice, e di imparare ad usare un debugger.
Lo pseudo codice va bene quando di fianco hai la maestra che legge e controlla quello che hai fatto.
Ad esempio qui c'e' un debugger C online con gia' il codice pre-caricato.
https://onlinegdb.com/xHyesZJtP

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define N 3
#define INFINITY 1000000000

int p[N] = {3, 6, 4};
int s[N] = {2, 3, 7};

int cost(int i, int t){
    printf ("%*c inizio cost con i = %d, t = %d \n", N-i, ' ', i, t);
    if (t <= 0) {
        printf("%*c t <= 0, return 0 \n", N-i, ' ');
        return 0;
    }
    if (i < 0) {
        printf("%*c i < 0, return inf \n", N-i, ' ');
        return INFINITY;
    }
    int a, b;
    printf("%*c chiamo cost con scelta giocatore \n", N-i, ' ');
    a = p[i] + cost(i - 1, t - s[i]);
    printf("%*c totale costo con scelta giocatore: %d \n", N-i, ' ', a);
    printf("%*c chiamo cost senza scelta giocatore \n", N-i, ' ');
    b = cost(i - 1, t);
    printf("%*c totale costo senza scelta giocatore: %d \n", N-i, ' ', a);
    if (a < b) {
        printf("%*c return a: %d\n", N-i, ' ', a);
        return a;
    } else {
        printf("%*c return b: %d\n", N-i, ' ', b);
        return b;
    }
}

int main()
{
    int c;
    c = cost(2, 5);
    printf("costo minimo: %d\n", c);
    return 0;
}

[Studente Anonimo]

Grazie mille, a dire la verità io so un po' di Java, C++ e MatLab. Però l'esame sarà su carta e il prof richiede pseudocodice.

[apatriarca]

@Quinzio: Il programma che hai scritto non rispetta le condizioni dell'esercizio (per quanto condivida la preferenza nell'usare linguaggi reali piuttosto che finti e mal definiti). La tua soluzione segue un approccio top-down (invece che bottom-up) e non è un approccio di programmazione dinamica. Hai infatti semplicemente convertito la definizione del costo in una funzione ricorsiva che calcola più volte la stessa cosa.

Per un approccio bottom-up dobbiamo costruire la soluzione partendo dalle soluzioni costanti e calcolare gli altri valori a partire da questi. Qualcosa come il seguente insomma:

C = D = {[0] 0, [t in 1 .. T] INFINITY }
for i in 1 .. N
  D[0] = 0
  for t in 1 .. (s[i] - 1)
    D[t] = min(C[t], p[i])
  for t in 1 .. T
    D[t] = min(C[t], p[i] + C[t - s[i]])
  swap(C, D)
result = C[T]

EDIT: Ho modificato il tuo codice per usare un metodo bottom-up: https://onlinegdb.com/U_XlWlIQ1