Compulsive Shopping (shopping)

(shopping)

Non riesco a capire come risolvere il problema shopping, ho pensato a una dp, ma non è possibile creare la memo per le dimensioni che andrebbe ad occupare.

Questo è il mio codice:

int memo[100007][1000007];
int n, e;

int rec(vi &v, int i, int e, bool prec) {
	if(i >= n)
		return e;
	if(memo[i][e] != -1)
		return memo[i][e];
	else if(v[i] > e)
		return memo[i][e] = rec(v, i+1, e, false);
	else if(prec)
		return memo[i][e] = max(
			rec(v, i+1, e-v[i], true),
			rec(v, i+1, e, false)
		);
	else 
		return memo[i][e] = rec(v, i+1, e-v[i], true);
}

int main() {

	cin >> n >> e;
	vi v(n);

	for(int &e : v)
		cin >> e;

	return cout << max(rec(v, 0, e, false), 
			rec(v, 0, (e - (e - v[0]) - 1), false)), 0;
}

Prova a spiegare la tua idea, con solo il codice è difficile aiutarti.
Siccome la memo risulta troppo grande puoi provare a ridurre la dimensione, magari rimuovendo qualche parametro inutile che puoi ricavarti.

In pratica il primo richiamo della funzione(che si trova al return del main) mi dovrebbe calcolare la soluzione migliore tra i 2 casi(se spendo prima di iniziare la passeggiata o meno).
Dopo di che nella funzione ‘rec’ i parametri sono:

  • v -> vettore di elementi;
  • i ->indice che sto processando
  • e -> il numero di euro rimasti fin ora
  • prec -> se ho acquistato l’elemento precedente o meno

Poi:

  1. Il primo ‘if’ mi controlla se sono attivato alla fine dell’array, quindi non ho altra scelta che ritornare il valore di ‘e’
  2. Il secondo controllerebbe se sono già stato in questa situazione (nel codice c’è scritto ‘!= -1’, in realtà è ‘!=0’)
  3. Il terzo controlla se l’item costa di più dei soldi che ho, quindi non posso acquistarlo e quindi vado al prossimo
  4. Il quarto controlla se ho acquistato il precedente e quindi faccio la scelta migliore tra l’acquisto del corrente o quello del prossimo
  5. Nell’ultimo caso lo acquisto perchè non ho altra scelta

Proviamo a ragionare sui parametri che identificano lo stato:

  • La posizione del item che stiamo considerando.
  • Il quantitativo di soldi al momento.
  • Se ho acquistato l’item precedente.

Del primo parametro non ne possiamo farne a meno, la posizione in cui ci troviamo adesso è fondamentale per capire se abbiamo elaborato quel elemento.
Il terzo parametro (se abbiamo acquistato l’item precedente) non aumenta drasticamente la complessità, può essere presente o anche no.
L’unico parametro su cui possiamo lavorare è la quantità di denaro che abbiamo al momento. Probabilmente ne si può fare a meno. Ti consiglio di stampare la tabella dei risultati intermedi e di vedere se ci sono informazioni ridondanti che puoi evitare. Potresti notare informazioni (in)utili :stuck_out_tongue:

Ci ho guardato e sì, hai ragione al posto di una memo N x E ne basta una N x 2(una per quando acquisto l’item e una per quando non la acquisto)(sempre se ho capito bene), poiché la memo rimane pressoché ripetitiva di 2 soli valori.
Ho provato a fare qualche cambiamento risolvendo il problema della memo, ma noto che mi da output not correct sull’80% dei testcase

vector<vi> memo;
int n, e;

int rec(vi &v, int i, int e, bool prec) {
	if(i >= n)
		return e;

    if(memo[i][0] != -1 && memo[i][1] != -1)
		return max(memo[i][0], memo[i][1]);

	else if(v[i] > e)
		return memo[i][0] = rec(v, i+1, e, false);

	else if(prec) {
        memo[i][0] = rec(v, i+1, e, false);
        memo[i][1] = rec(v, i+1, e-v[i], true);

        return max(memo[i][0], memo[i][1]);
    }

	else return memo[i][1] = rec(v, i+1, e-v[i], true);
}

int main() {

	cin >> n >> e;
	vi v(n);

	for(int &e : v)
		cin >> e;

    memo = vector<vi>(n + 1, vi(2, -1)); 

    cout << max(
        rec(v, 0, e, false), 
		rec(v, 0, (e - (e - v[0]) - 1), false)
    ) << '\n';

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < 2; j++){
			cout << memo[i][j] << ' ';
		}
        cout << '\n';
	}

	return system("pause"), 0;
}

Si, hai capito bene.

Non sono molto convito di questo statement. Non puoi farti restituire il massimo tra non comprare l’item e comprarlo. Ricordati che puoi utilizzare la memo di non comprarlo solo se hai comprato precedentemente.

if(memo[i][0] != -1 && memo[i][1] != -1) return max(memo[i][0], memo[i][1]);
Non sono molto convito di questo statement. Non puoi farti restituire il massimo tra non comprare l’item e comprarlo. Ricordati che puoi utilizzare la memo di non comprarlo solo se hai comprato precedentemente

Si è vero, ma dopo aver controllato se ho comprato precedentemente devo comunque ritornare il massimo stra i due, (sempre se li ho calcolati)

tipo così:

if(prec && memo[i][0] != -1 && memo[i][1] != -1)
    return max(memo[i][0], memo[i][1]);

else if(memo[i][1] != -1) 
    return memo[i][1];