Cod sursa(job #901082)
Utilizator | Bura Bogdan nosurrender99 | Data | 1 martie 2013 00:07:43 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.54 kb |
#include <fstream>
#include <iostream>
using namespace std;
fstream f("rucsac.in" , ios::in), fo("rucsac.out", ios::out);
int mat[3][10001];
int main()
{
int n,g,v,w,in=1,ma;
f>>n>>g;
for(int i=1;i<=n;i++)
{
f>>w>>v;
for(int j=w;j<=g;j++)
{
if(mat[i%2-in][j-w]+v>mat[i%2-in][j])
mat[i%2][j]=mat[i%2-in][j-w]+v;
else
mat[i%2][j]=mat[i%2-in][j];
}
in=-in;
ma=mat[i%2][g];
}
fo<<ma;
return 0;
}