Pranzo dalla nonna 60/100

Aiuto
1

Ciao, stavo provando a risolvere pranzo dalla nonna ma ottengo solo 60/100 per via del tempo di esecuzione. Questo è il codice:

int na = 1000000000;

int mangia(int N, int K, int P[], int index, std::map<int, int> map) {

	if (K <= 0) {
		return 0;
	}
	else if (N == index) {
		return na;
	}
	else if (map.find(index) != map.end()) {
		return map[index];
	}
	else {
		int answer = std::min(
			mangia(N, K, P, index + 1, map),
			mangia(N, K - P[index], P, index + 1, map) + P[index]
		);
		map[index] = answer;
		return answer;
	}

}


int P[MAXN];

int main() {
	FILE* fr, * fw;
	int N, K, i;

	fr = fopen("input.txt", "r");
	fw = fopen("output.txt", "w");
	assert(2 == fscanf(fr, "%d %d", &N, &K));
	for (i = 0; i < N; i++)
		assert(1 == fscanf(fr, "%d", &P[i]));

	fprintf(fw, "%d\n", mangia(N, K, P, 0, {}));
	fclose(fr);
	fclose(fw);
	return 0;
}

Riesco ad avvicinarmi molto al tempo richiesto ma non sono riuscito ad ottimizzarlo abbastanza da prendere 100/100. Qualcuno ha qualche idea?

2

Ciao, mi pare di capire che il tuo algoritmo risolva il problema tramite brute force. Esce di tempo perchè la complessità di un algoritmo del genere è esponenziale. Dovresti trovare una soluzione con complessità minore, ovvero O(KN) tramite programmazione dinamica.
Soluzione → Guarda knapsack problem: stesso problma ma al posto di avere la maggiore somma <= a K, devi adattarlo leggermente per avere la minore somma >= a K
→ Qua trovi una spiegazione decente

1 Mi Piace
3

Grazie, sono riuscito a risolvere!

1 Mi Piace