DP: ricostruire la soluzione

Aiuto
1

Di solito, nei problemi di Programmazione Dinamica in cui serve ricostruire la soluzione migliore, l’unico metodo che mi è sempre venuto in mente è quello di costruirmi una specie di “lista” con una struct che viaggia passo passo per i vari stati del problema…ma questo metodo occupa tanta memoria e in lucky numbers, dove la mia soluzione ha 10000*10000 stati, non è sufficiente a fare 100/100 ma mi da 50/100 appunto per problemi di memoria…
Come si puo fare per costruire la soluzione senza problemi di memoria?

Codice:

#include<bits/stdc++.h>

using namespace std;

struct nodo{
	int n;
	nodo* next;
};

int K, C;
int dp[10000][10000];
nodo build[10000][10000];
bool lucky[10000];
set<int> s;

int value(int i, int num){
	if(i==C){
		build[i][num].next=NULL;
		if(lucky[num]) return 1;
		return 0;
	}
	
	if(dp[i][num]!=-1)
		return dp[i][num];
		
	int &res = dp[i][num];
	res = (lucky[num]==true ? 1 : 0);
	
	int base=num%1000;
	base*=10;
	
	int plus=res;
	for(int it=0; it<10; it++){
	    int p=value(i+1, base+it)+plus;
	    if(p>res){
	    	res=p;
	    	build[i][num].next=&build[i+1][base+it];
	    	build[i+1][base+it].n=it;
		}
	}
	
	return res;
}

int main(){
	
	ifstream in("input.txt");
	ofstream out("output.txt");
	
	in>>K>>C;
	
	for(int i=0; i<K; i++){
		int num;
		in>>num;
		
		lucky[num]=true;
		s.insert(num);
	}
	
	for(int i=0; i<C; i++){
		for(int j=0; j<10000; j++){
			dp[i][j]=-1;
		}
	}
	
	nodo* next;
	int primo;
	int res=0;
	for(auto x:s){
		int p=value(4, x);
		if(p>=res){
			res=p;
			primo=x;
			next=build[4][x].next;
		}
	}
	
	out<<primo;
	while(next!=NULL){
		out<<next->n;
		next=next->next;
	}
	
	return 0;
}
2

Scusa il codice a che problema si riferisce?

3

Si riferisce a lucky numbers

4

Mi sono confuso, credo che il problema sia dovuto alla funzione ricorsiva…comunque come faccio a fare questa funzione in modo iterativo tenendo conto anche che c’è un dato da ritornare ? Non ci salto più fuori

5

Per ricavare la soluzione dalla memo(la tabella dei risultati) hai due strade:

  1. Tenersi una tabella ausiliaria in cui salvi la scelta migliore che hai per quello stato.
  2. Visitare ogni stato in cui puoi avanzare da quello attuale e scegliere quello migliore.

Nel primo caso basta effettuare la scelta migliore per transitare nello stato successivo.
La soluzione puoi costruirla sia iterativamente che ricorsivamente, scegli la strada più comoda.
Ora per risolvere lucky numbers hai bisogno di ridurre l’utilizzo di memoria. Guarda bene le assunzioni, cosa può aiutarti? Se non ti viene in mente niente, prova a rappresentare graficamente la tabella dp, ci sono informazioni ridondanti/inutili che puoi evitare?

6

Grazie, davo per scontato che il problema fosse solo di memoria invece anche la complessita era troppo alta. Ora sono riuscito a fare 80/100 con una tabella C x K, non riesco a fare l’ultimo subtask perchè in ogni stato c’è un ciclo lungo K (cerco di attaccare alla sequenza tutti i numeri) quindi la complessita sarebbe C x K x K. Come potrei fare?

7

Credo che la soluzione voluta sia proprio O(C * K^2), aggiungendo la parola chiave inline dovresti riuscir a far 100. Ecco un esempio:

inline int somma(int a, int b){
    return a + b;
}

Se vuoi sapere cosa fa esattamente cerca materiale online. Se non hai intenzione di usarla, dovresti implementare la dp iterativamente. Implementare entrambi le versioni è un buon esercizio :slight_smile:

8

La keyword inline ormai è abbastanza inutile e viene ignorata dal compilatore, pertanto aggiungerla o meno non dovrebbe influire sul punteggio.
Più dettagli.

5 Mi Piace