Cod sursa(job #642927)
Utilizator | Data | 2 decembrie 2011 16:28:55 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.44 kb |
#include<fstream>
using namespace std;
int n,g,v[10100],mx;
int main() {
int i,x,y,j;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
in>>n>>g;
v[0]=1;
for(i=0;i<n;i++) {
in>>y>>x;
for(j=min(mx,g-y);j>=0;j--)
if(v[j]&&v[j+y]<v[j]+x) {
v[j+y]=v[j]+x;
if(j+y>mx)
mx=j+y;
}
}
for(i=g;i>=0;i++)
if(v[i]) {
out<<v[i]-1<<'\n';
break;
}
in.close();
out.close();
return 0;
}