Cod sursa(job #1375573)

Utilizator cristianajelerJeler Cristiana Ioana cristianajeler Data 5 martie 2015 13:40:07
Problema Problema rucsacului Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <iostream>
#include<fstream>
using namespace std;
int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    int m[5000], c[5000], a[20000], d[20000] ;
    int n, G,i,max=0,k;
    f>>n>>G;
   for(i=1; i<=n; i++)
    {
       f>>m[i]>>c[i];
     }
   for(i=1; i<=2*G; i++) a[i]=d[i]=0;
   a[m[1]]=c[1];
   for(k=2; k<=n; k++)
   {
    for(i=1; i<=G; i++)
    {
        if(a[i+m[k]]<a[i]+c[k]) d[m[k]+i]=a[i]+c[k];
    }
    for(i=1; i<=G;i++)
        a[i]=d[i];
   }
   for(i=1; i<=G; i++)
   {
       if(d[i]>max) max=d[i];
   }
    g<<max;
    g.close();
}