# Pranzo dalla nonna 60/100

**URL:** <https://forum.olinfo.it/t/pranzo-dalla-nonna-60-100/7577>\
**Category:** Aiuto\
**Created:** [16 Luglio 2022, 1:31pm UTC](https://forum.olinfo.it/t/pranzo-dalla-nonna-60-100/7577 "2022-07-16T13:31:14Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![DanieleSahebi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/3da27b/32.png) [@DanieleSahebi](https://forum.olinfo.it/u/DanieleSahebi)\
**Post date:** [16 Luglio 2022, 1:31pm UTC](https://forum.olinfo.it/t/pranzo-dalla-nonna-60-100/7577/1 "2022-07-16T13:31:15Z")

</div>

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

```auto
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?

---

<div class="post-metadata">

**Author:** ![MatteoArcari](https://forum.olinfo.it/user_avatar/forum.olinfo.it/matteoarcari/32/1976_2.png) [@MatteoArcari](https://forum.olinfo.it/u/MatteoArcari)\
**Post date:** [16 Luglio 2022, 6:52pm UTC](https://forum.olinfo.it/t/pranzo-dalla-nonna-60-100/7577/2 "2022-07-16T18:52:43Z")

</div>

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](https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/) trovi una spiegazione decente

---

<div class="post-metadata">

**Author:** ![DanieleSahebi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/3da27b/32.png) [@DanieleSahebi](https://forum.olinfo.it/u/DanieleSahebi)\
**Post date:** [17 Luglio 2022, 3:23pm UTC](https://forum.olinfo.it/t/pranzo-dalla-nonna-60-100/7577/3 "2022-07-17T15:23:23Z")

</div>

Grazie, sono riuscito a risolvere!