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<bits/stdc++.h>
using namespace std;
ifstream fin("input.txt");
ofstream fout("output.txt");
int shopping(vector<int> &p, vector<int> &memoA, vector<int> &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<n;++i){
if(flag&&(memoB[i-1]>=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<int> price(n);
vector<int> memoA(n);
vector<int> memoB(n);
for(int i=0;i<n;++i)
fin>>price[i];
/*cout<<shopping(price, memoA, memoB, n, e)<<"\n";
for(int i=0;i<n;++i)
cout<<memoA[i]<<" ";
cout<<"\n";*/
for(int i=e;i>res;--i)
res=max(res, shopping(price, memoA, memoB, n, i));
fout<<max(res, shopping(price, memoA, memoB, n, e))<<"\n";
return 0;
}