Lo zaino di Aladdin#1661

Lo zaino di Aladdin (Editoriale)

Sia $d p_{k} [s]$ dp_k[s] — il costo massimo di un carico di peso non superiore a $s$ , se è permesso utilizzare soltanto oggetti dei primi $k$ tipi.

Consideriamo due possibili varianti nella composizione di un carico di peso $i$ :

Non utilizzare l'oggetto di tipo $k$ : in questo caso il valore ottimale non cambia, cioè

d p_{k} [i] = d p_{k - 1} [i]

dp_k[i] = dp_{k - 1}[i]

Utilizzare l'oggetto di tipo $k$ : allora il suo peso $w_{k}$ w_k occuperà una parte della capacità dello zaino, e il costo aumenterà di $v_{k}$ v_k, cioè

d p_{k} [i] = d p_{k} [i - w_{k}] + v_{k} .

dp_k[i] = dp_k[i - w_k] + v_k.

Poiché è richiesto massimizzare il costo del carico, otteniamo la relazione ricorrente:

d p_{k} [i] = ma x (d p_{k - 1} [i], d p_{k} [i - w_{k}] + v_{k}), w_{k} \leq i \leq s

dp_k[i] = max(dp_{k - 1}[i], dp_k[i - w_k] + v_k), w_k \le i \le s

Casi base:

d p_{0} [i] = 0 e d p_{k} [0] = 0

dp_0[i] = 0~e~dp_k[0] = 0

Sia la funzione $f (k, s)$ f(k, s) che calcola il costo massimo del carico che si può raccogliere in uno zaino di peso non superiore a $s$ , usando i primi $k$ tipi di oggetti. Allora vale la relazione ricorrente:

f (k, s) = ma x (f (k - 1, s), f (k, s - w [k]) + v [k])

f(k, s) = max(f(k - 1, s), f(k, s - w[k]) + v[k])

Resta da calcolare il valore della funzione $f (k, s)$ f(k, s) usando la memoizzazione.

Implementazione dell'algoritmo

Dichiariamo gli array di lavoro:

$w [i]$ — il peso dell'oggetto di tipo $i$ ;
$p [i]$ — il costo dell'oggetto di tipo $i$ ;
$d p [i]$ — il costo massimo del carico di peso non superiore a $i$ ;

#define MAXW 252
#define MAXN 37
int w[MAXN], p[MAXN];
int dp[MAXW];

Leggiamo i dati in ingresso.

scanf("%d %d", &s, &n);
for (i = 0; i < n; i++)
  scanf("%d %d", &w[i], &p[i]);

Elaboriamo in sequenza gli $n$ tipi di oggetti.

for (k = 0; k < n; k++)
{

Ricalcoliamo i valori dell'array $d p$ , tenendo conto della possibilità di utilizzare oggetti di tipo $k$ . Poiché il numero di oggetti di ciascun tipo non è limitato, ogni oggetto può essere scelto più volte.

  for (i = w[k]; i <= s; i++)
    dp[i] = max(dp[i], dp[i - w[k]] + p[k]);
}

Stampiamo la risposta.

printf("%d\n", dp[s]);

Implementazione dell'algoritmo — ricorsione

Dichiariamo gli array di lavoro:

$w [i]$ — il peso dell'oggetto di tipo $i$ ;
$p [i]$ — il costo dell'oggetto di tipo $i$ ;
$d p [i]$ — il costo massimo del carico di peso non superiore a $i$ ;

#define MAXW 252
#define MAXN 37
#define INF 2000000000
int w[MAXN], v[MAXN];
int dp[MAXN][MAXW];

La funzione $f (k, s)$ f(k, s) calcola il costo massimo del carico che si può raccogliere in uno zaino di peso non superiore a $s$ , usando i primi $k$ tipi di oggetti.

int f(int k, int s)
{

Se $k = 0$ k = 0 oppure $s = 0$ s = 0, allora lo zaino è vuoto, e il suo costo è pari a $0$ .

  if (k == 0 || s == 0) return 0;

Se $s < 0$ s < 0, allora abbiamo superato il peso consentito, e questa variante non ha senso. Perciò restituiamo $- I N F$ ( $I N F$ — è un certo numero grande).

  if (s < 0) return -INF;

Se il valore $f (k, s)$ f(k, s) è già stato calcolato, allora lo restituiamo.

  if (dp[k][s] != -1) return dp[k][s];

Calcoliamo il valore $f (k, s)$ f(k, s) e lo memorizziamo in $d p [k] [s]$ dp[k][s].

  return dp[k][s] = max(f(k - 1, s), f(k, s - w[k]) + v[k]);
}

Parte principale del programma. Leggiamo i dati in ingresso.

scanf("%d %d", &s, &n);
for (i = 1; i <= n; i++)
  scanf("%d %d", &w[i], &v[i]);

Calcoliamo e stampiamo la risposta.

memset(dp, -1, sizeof(dp));
printf("%d\n", f(n, s));