Cod sursa(job #2928311)
Utilizator | Andrei Gagea Andrei_Gagea08 | Data | 22 octombrie 2022 18:38:52 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.66 kb |
#include <fstream>
#define INF 50000000
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
long long b[11];
int main()
{
int n,i,j;
int maxi=0;
int G,g,p;
cin>>n>>G;
for(i=1;i<=G;i++)
{
b[i]=-INF;
}
for(j=1;j<=n;j++)
{
cin>>g;
cin>>p;
for(i=min(G-g,maxi);i>=0;i--)
{
if(b[i+g]<b[i]+p)
b[i+g]=b[i]+p;
if(i+g>maxi)
maxi=i+g;
}
}
i=maxi;
maxi=0;
for(;i>=0;i--)
{
if(b[i]>maxi)
maxi=b[i];
}
cout<<maxi;
return 0;
}