Puoi leggere e provare a risolvere questo problema visitando questo indirizzo: territoriali.olinfo.it
Un prerequisito per risolvere questo task è conoscere la tecnica della Programmazione Dinamica. Se non la conosci, puoi impararla leggendo la Guida alle selezioni territoriali.
Il problema in questione è riconducibile al più classico "problema dello zaino" (Knapsack Problem) in particolare nella sua versione "0-1" che sta a indicare "prendo / non prendo" (nel senso che non è ammesso prendere, per esempio, solo metà di un processore dimezzandone quindi il costo ed il numero di core).
La soluzione per questo problema consiste nel modellare la risposta alla domanda (ovvero: il massimo numero di core ottenibili rientrando nel budget) con una funzione ricorsiva della forma f(b, n) dove:
È immediato vedere che una volta che la funzione f(b, n) è pronta ed implementata, ci basta semplicemente calcolare f(B, N) per ottenere il risultato cercato (nota che qui le variabili in maiuscolo sono i dati di input, descritti nel testo del problema!)
Per implementare la funzione f(b, n) dobbiamo cercare, come in tutti i problemi di programmazione dinamica, una relazione di ricorrenza: un'espressione che ci permetta di calcolare f(b, n) a partire da una o più chiamate ad f() con valori dei parametri generalmente minori o uguali (naturalmente almeno uno dei parametri sarà minore, altrimenti si entrerebbe in una ricorsione infinita).
Una possibile definizione è data da:
f(b, 0) = 0
Infatti, avendo a disposizione 0 processori possiamo ottenere al massimo 0 core.
f(b, n) = f(b, n - 1) se il costo del processore n-esimo è maggiore del limite corrente b
Infatti, dato che il limite di budget che abbiamo imposto non è sufficiente ad acquistare l'ultima CPU della lista, tanto vale richiamare la funzione che ci dà il massimo numero di core senza però considerare l'ultima CPU!
f(b, n) = max(f(b - costo[n], n - 1) + numero_core[n], f(b, n - 1)) se il costo del processore n-esimo è minore o uguale al limite corrente b
Infatti, dato che il limite di budget che abbiamo imposto è sufficiente ad acquistare l'ultima CPU della lista, il numero massimo di core ottenibili con il budget rimanente è dato da f(b - costo[n], n - 1) + numero_core[n]; tuttavia, non è detto che acquistare l'n-esima CPU sia la scelta giusta, per cui, "giusto per sicurezza", proviamo anche a non prendere tale CPU e scegliamo il massimo tra i due risultati.
Solitamente questa soluzione è più che sufficiente, ma per via dei limiti imposti nel problema (in particolare sul massimo budget possibile: 1000000000) tale soluzione molto probabilmente andrà fuori memoria. Gli "stati" della programmazione dinamica sono infatti BxN ovvero 300000000000. Ogni stato è un numero intero a 32 bit (4 byte) quindi la memoria RAM necessaria per calcolare la soluzione al caso pessimo sarà: 300000000000 * 4 / 230 = 1117.6 GB, assolutamente troppo per qualsiasi PC che si può trovare in casa (o a scuola) nel 2019 😩
La soluzione descritta sopra prende dei punti, ma non tutti. Per prendere tutti i punti è infatti necessario attaccare il problema da un altro "punto di vista". Invece di spezzare la soluzione usando un parametro "b" che va a limitare il budget, ribaltiamo la formula (╯°□°）╯︵ ┻━┻ e chiediamo invece qual è il minimo budget possibile che ci permette di raggiungere un determinato numero di core totali.
L'idea, quindi, è di spostare il "numero di core" da risultato della funzione a parametro della funzione, e allo stesso tempo spostare il budget nel senso opposto (da parametro a risultato). Questo trucchetto è utile solo perché il numero massimo di core totali specificato dal testo del problema (300 * 200 = 60000) è un numero molto più piccolo del massimo budget (1000000000) e quindi è più adatto ad essere un parametro.
Quindi, definiamo una funzione ricorsiva g(c, n) simile a f(b, n) ma con un parametro c che stavolta limita il numero di core totali. Inoltre, il valore di g(c, n) ora sta ad indicare il budget minimo richiesto per acquistare una quantità "c" di core usando i primi "n" processori. Nota bene: prima era immediato vedere che una volta implementata la funzione f(b, n) ci bastava semplicemente calcolare f(B, N), ma stavolta non ci basta più fare una sola chiamata alla funzione g(c, n) per calcolare la soluzione. Dovremo infatti provare tutti i possibili valori di "c", e poi stampare quello più alto trovato tale che g(c, N) è minore o uguale a B.
Detto questo, non ci resta che definire la funzione g(c, n). Un modo di definirla è:
g(0, n) = 0
Infatti, per ottenere 0 core totali ci basta anche un budget pari a 0.
g(c, n) = g(c, n - 1) se il numero di core del processore n-esimo è maggiore del limite corrente c
Infatti, dato che il limite sul numero di core che abbiamo imposto non ci permette di acquistare l'ultima CPU della lista, tanto vale richiamare la funzione che ci dà il minimo budget possibile per raggiungere lo stesso numero di core senza però considerare l'ultima CPU!
g(c, n) = min(costo[n] + g(c - numero_core[n], n - 1), g(c, n - 1)) se il numero di core del processore n-esimo è minore o uguale al limite corrente c
Infatti, dato che il processore n-esimo non ci fa "sforare" il limite sul numero di core che ci siamo imposti, lo prendiamo e quindi usiamo un budget pari al costo di tale CPU: sommiamo quindi questo valore al budget necessario per ottenere i core rimanenti, che è dato da g(c - numero_core[n], n - 1); analogamente a ciò che è successo la scorsa volta, anche stavolta non è detto che acquistare l'n-esima CPU sia la scelta giusta, per cui, "giusto per sicurezza", proviamo anche a non prendere tale CPU e scegliamo il minimo tra i due risultati.
g(c, 0) = ∞ se il limite corrente c è maggiore di 0
Questo è un trucco (che funziona perché stiamo usando la funzione min) che serve a marcare questa situazione come non valida: in parole povere stiamo dicendo alla nostra programmazione dinamica di non scegliere mai un "percorso ricorsivo" che ci porta a questa situazione (dato che non è possibile ottenere un numero positivo di core totali quando non ci sono più CPU disponibili!)
La soluzione in programmazione dinamica appena descritta ha un numero di stati pari a 60000x300 ovvero 18000000, per un'occupazione di RAM circa pari a: 18000000 * 4 / 220 = 68.6 MB. Circa la stessa quantità di RAM utilizzata per una singola scheda del browser col quale stai leggendo questo testo 🤓
#include <iostream>
#include <vector>
using namespace std;
const int VERYBIG = 1000000001; // just bigger than B is enough
// using something too big is risky
// (could overflow when adding to it...)
vector<int> costo, numero_core;
vector<vector<int>> memo;
int g(int c, int n) {
if (c == 0) return 0;
if (n == 0) return VERYBIG;
if (memo[c][n] != -1) return memo[c][n];
if (numero_core[n - 1] > c) {
memo[c][n] = g(c, n - 1);
return memo[c][n];
} else {
memo[c][n] = min(costo[n - 1] + g(c - numero_core[n - 1], n - 1), g(c, n - 1));
return memo[c][n];
}
}
int main() {
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
costo.clear();
numero_core.clear();
memo.clear();
int N, B;
cin >> N >> B;
costo.resize(N);
numero_core.resize(N);
int core_totali = 0;
for (int i = 0; i < N; i++) {
cin >> numero_core[i] >> costo[i];
core_totali += numero_core[i];
}
memo.resize(core_totali + 1, vector<int>(N + 1, -1)); // matrice piena di -1
for (int soluzione = core_totali; soluzione >= 0; soluzione--) {
if (g(soluzione, N) <= B) {
cout << "Case #" << t << ": " << soluzione << endl;
break;
}
}
}
}
La soluzione descritta sopra ovviamente è più che sufficiente a totalizzare tutti i punti. Tuttavia, volendo, c'è una soluzione che riduce ulteriormente la memoria (senza però velocizzare significativamente l'esecuzione) facendo uso di un solo parametro. Esercitati a trovarla!