Cod sursa(job #3200389)
| Utilizator | Data | 4 februarie 2024 15:06:00 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.55 kb |
// #include <iostream>
#include <fstream>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int n,gmax;
int g[5002],p[5002],mat[5002][10002];
int main()
{
cin>>n>>gmax;
for(int i=1;i<=n;++i)
cin>>g[i]>>p[i];
for(int i=1;i<=n;++i)
for(int j=0;j<=gmax;++j){
int l=i%2;
mat[l][j]=mat[1-l][j];
if(j>=g[i])
mat[l][j]=max(mat[l][j],p[i]+mat[1-l][j-g[i]]);
}
cout<<mat[n%2][gmax];
return 0;
}