Cod sursa(job #1462600)
Utilizator | Data | 18 iulie 2015 16:29:48 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.58 kb |
#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int d[10001];
int main()
{
int n,G,g,p,smax,profit,i,j;
in>>n>>G;
for(i=1;i<=G;i++)
d[i]=-1;
smax=0;
for(i=1;i<=n;i++)
{
in>>g>>p;
for(j=smax;j>=0;j--)
if(d[j]!=-1 and j+g<=G)
{
if(d[j+g]<d[j]+p)
d[j+g]=d[j]+p;
if(j+g>smax)
smax=j+g;
}
}
profit=0;
for(i=G;i>=1;i--)
if(d[i]>profit)
profit=d[i];
out<<profit;
return 0;
}