# Problema con shopping 60/100 **URL:** \ **Category:** Aiuto\ **Created:** [5 Agosto 2020, 9:28pm UTC](https://forum.olinfo.it/t/problema-con-shopping-60-100/6258 "2020-08-05T21:28:38Z")\ **Posts on this page:** 6\ **Page:** 1
**Author:** ![Goldini](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/a4c791/32.png) [@Goldini](https://forum.olinfo.it/u/Goldini)\ **Post date:** [5 Agosto 2020, 9:28pm UTC](https://forum.olinfo.it/t/problema-con-shopping-60-100/6258/1 "2020-08-05T21:28:38Z")
Sto provando a risolvere il problema compulsive shopping solo che non riesco a capire a come applicare correttamente la programmazione dinamica. All’inizio ho tentato un approccio top down con memoizzazione (con l’utilizzo di una map), poi a causa della poca memoria e di diversi timeout sono passato ad una bottom up. Grazie a due array (uno contiene il risultato per un certo n escludendo l’iesimo numero l’altro includendolo) sono “riuscito” a calcolare il numero massimo di soldi rimanenti partendo da un budget E. Questo mi richiede una complessità O(n). Ho difficoltà nel capire come calcolare efficientemente invece il numero di soldi da sprecare prima di acquistare i diversi prodotti. Qualche consiglio? Questo è il codice: ``` #include using namespace std; ifstream fin("input.txt"); ofstream fout("output.txt"); int shopping(vector &p, vector &memoA, vector &memoB, int n, int e) { bool flag=false; if(e>=p[0]){ memoA[0]=e-p[0]; memoB[0]=e-p[0]; } else{ memoA[0]=e; memoB[0]=e; flag=true; } for(int i=1;i=p[i]||memoA[i-1]>=p[i])){ memoB[i]=max(memoA[i-1]-p[i], memoB[i-1]-p[i]); if(memoA[i-1]>=p[i]) memoA[i]=memoA[i-1]-p[i]; else memoA[i]=memoA[i-1]; flag=false; } else if((memoB[i-1]>=p[i]||memoA[i-1]>=p[i])){ memoA[i]=memoB[i-1]; memoB[i]=max(memoA[i-1]-p[i], memoB[i-1]-p[i]); flag=false; } else{ memoA[i]=memoA[i-1]; memoB[i]=memoB[i-1]; flag=true; } } return max(memoA[n-1], memoB[n-1]); } int main() { int n, e, res=0; fin>>n>>e; vector price(n); vector memoA(n); vector memoB(n); for(int i=0;i>price[i]; /*cout<res;--i) res=max(res, shopping(price, memoA, memoB, n, i)); fout< **Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [7 Agosto 2020, 9:39am UTC](https://forum.olinfo.it/t/problema-con-shopping-60-100/6258/2 "2020-08-07T09:39:26Z") L’osservazione fondamentale è che se arrivo ad un certo articolo P\_i con certo budget E\_i posso fare due cose: - acquistare l’articolo ottentendo un budget di E\_i - P\_i euro, - sprecare prima della camminata abbastanza soldi in modo da ottenere un budget di P\_i - 1 soldi quando arrivo a tale articolo non potendolo perciò comprare. ---
**Author:** ![Goldini](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/a4c791/32.png) [@Goldini](https://forum.olinfo.it/u/Goldini)\ **Post date:** [8 Agosto 2020, 1:21pm UTC](https://forum.olinfo.it/t/problema-con-shopping-60-100/6258/4 "2020-08-08T13:21:53Z")
Ciò riflettuto un po’ e non mi sono chiare diverse cose. 1. Arrivato ad un certo articolo non c’è anche una terza cosa che posso fare? Ossia non acquistare l’articolo se ho acquistato il precedente. 2. Come faccio a capire se è possibile arrivare ad un certo articolo con un budget Pi -1. Come faccio ad essere sicuro che affinchè ci arrivi il budget iniziale sia minore di E. Per esempio se ho: 3 35 20 35 10 Arrivato all’articolo 35 potrei non comprarlo arrivandoci con un budget di 34 però per fare ciò dovrei avere un budget iniziale di 54 ma ciò non può essere fatto perchè quello iniziale in input è 35. ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [8 Agosto 2020, 5:05pm UTC](https://forum.olinfo.it/t/problema-con-shopping-60-100/6258/5 "2020-08-08T17:05:33Z")
> [@Goldini](#): > > Come faccio ad essere sicuro che affinchè ci arrivi il budget iniziale sia minore di E Non devi basarti sul budget iniziale ma solo sui valori del massimo budget possibile ottenuti per l’articolo precedente, proprio come nel tuo codice sopra. Se almeno uno tra `memoA[i-1]` e `memoB[i-1]` è maggiore o uguale a P\_i allora è possibile ottenere un budget di P\_i-1. ---
**Author:** ![Goldini](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/a4c791/32.png) [@Goldini](https://forum.olinfo.it/u/Goldini)\ **Post date:** [9 Agosto 2020, 4:20pm UTC](https://forum.olinfo.it/t/problema-con-shopping-60-100/6258/6 "2020-08-09T16:20:49Z")
Sono riuscito a risolverlo grazie mille. Potresti consigliarmi dei problemi di programmazione dinamica da svolgere per prepararmi per le territoriali? ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [10 Agosto 2020, 8:07am UTC](https://forum.olinfo.it/t/problema-con-shopping-60-100/6258/7 "2020-08-10T08:07:07Z")
Il miglior problema su cui allenarsi è senza dubbio [Festival del GCD](https://training.olinfo.it/#/task/fpb/statement) anche se è un po’ difficile. Per altri problemi puoi cercare mediante il [tag dp](https://training.olinfo.it/#/tasks/1?tag=dp).