Cod sursa(job #2429281)
| Utilizator | Data | 8 iunie 2019 20:11:12 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 0 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.72 kb |
#include<fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int s[10001];
struct ura{
int g,c;};
ura v[5001];
int main(){
int n,gmax,v1,g1,i,j,max;
in>>n>>gmax;
for(i=1;i<=n;i++)
{
in>>g1>>v1;
v[i].g=g1;
v[i].c=v1;
}
max=0;
for(i=1;i<=n;i++)
{
for(j=max;j>=1;j--)
{
if(s[j]!=0)
if(j+v[i].g<=gmax)
if(s[j]+v[i].c>s[j+v[i].g])s[j+v[i].g]=s[j]+v[i].c;
}
if(max+v[i].g>gmax)max=gmax;
else max=max+v[i].g;
if(s[v[i].g]<v[i].c)s[v[i].g]=v[i].c;
}
out<<s[gmax];
return 0;
}
