Cod sursa(job #1174171)
Utilizator | Data | 22 aprilie 2014 11:35:54 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 35 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include<fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int W[10001],P[10001],sol[5001][10001],N,G;
int main()
{
in>>N>>G;
int i,j;
for(i = 1 ; i <= N ; i++)
in>>W[i]>>P[i];
for(i = 1 ; i <= N ; i++)
for ( j = 0 ; j <= G ; j++)
{
sol[i][j] = sol[i-1][j];
if(W[i] <= j)
sol[i][j] = max(sol[i-1][j],sol[i-1][j-W[i]]+P[i]);
}
out<<sol[N][G];
in.close();
out.close();
return 0;
}