Cod sursa(job #810826)
Utilizator | Eternal Heroe EternalHeroe | Data | 11 noiembrie 2012 06:24:56 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.46 kb |
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,gt,i,w,p,j,m,a[100002];
int main(){
f>>n>>gt;
f>>w>>p;
a[w]=p;
m=p;
for(i=1;i<n;i++)
{
f>>w>>p;
for(j=gt-w;j>=0;j--)
{
if((a[j]||j==0)&&j+w<=gt)
{
if(a[j+w])
{
if(a[j]+p>a[j+w])
{
a[j+w]=a[j]+p;
}
}
else a[j+w]=a[j]+p;
}
}
}
for(i=1;i<=gt;i++)
{
if(a[i]>m)
m=a[i];
}
g<<m<<"\n";
}