As vrea sa stiu de ce urmatoare sursa nu obtine decat 0 p la problema http://www.infoarena.ro/problema/energii
<i> </i>#include <fstream> using namespace std; ifstream f("energii.in"); ofstream g("energii.out"); int INF=(1<<30),G,w,d[1002][5002],o,l,e,c,i,n,j; int main() { f>>n>>G; for (i=0;i<=n;i++) for (j=1;j<=G;j++) d[i][j]=INF; for (i=1;i<=n;i++) { f>>e>>c; for(j=1;j<=G;j++) if (e<=j) d[i][j]=min(d[i-1][j],d[i-1][j-e]+c); else d[i][j]=min(d[i-1][j],c); } if (d[n][G]==INF) g<<-1<<'\n'; else g<<d[n][G]<<'\n'; return 0; }
Hint: Memoria nu-ti permite. Foloseste 2 vectori. Ar tb sa schimbi si gandirea nu e un greedy clasic al problemei rucsacului e un pic diferit.