Cod sursa(job #2696141)
Utilizator | Sandor Stefan YolloSteff | Data | 15 ianuarie 2021 14:00:03 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.65 kb |
#include <fstream>
#include <algorithm>
using namespace std;
struct eu
{
int gr, val;
};
eu v[5001];
int sum[10001];
int main(){
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int i, n, gmax, s=0, j, maxx;
cin >> n >> gmax;
for(i=1;i<=n;i++)
{
cin >> v[i].gr >> v[i].val;
}
for(i=1;i<=n;i++)
{
for(j=gmax-v[i].gr; j>=0; j--)
{
if(sum[j]!=0||j==0)
sum[j+v[i].gr]=max(sum[j+v[i].gr],sum[j]+v[i].val);
}
}
maxx=-1;
for(i=1;i<=gmax;i++)
if(sum[i]>maxx)
maxx=sum[i];
cout << maxx;
return 0;
}