Cod sursa(job #1368572)
Utilizator | Alex Bercea Alex1199 | Data | 2 martie 2015 18:36:00 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.45 kb |
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n, w, m[5009],c[10009], V[2][10009],k, h;
int main()
{
f>>n>>w;
for(int i=1;i<=n;i++)
{f>>m[i]>>c[i];}
k=1; h=0;
for(int i=1;i<=n;i++)
{
if(i%2) {k=1; h=0;}
else {k=0;h=1;}
for(int j=1;j<=w;j++)
{
if(j<m[i]) V[k][j]=V[h][j];
else V[k][j]=max(V[h][j],V[h][j-m[i]]+c[i]);
}
}
g<<V[0][w];
return 0;
}