Cod sursa(job #682663)
Utilizator | Data | 19 februarie 2012 12:50:55 | |
---|---|---|---|
Problema | Problema rucsacului | Scor | 85 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.43 kb |
#include <fstream>
using namespace std;
int sol[10005];
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int main()
{
int n, g, greutate,cost;
fin>>n >>g;
int maxim=0;
while(n>0)
{
fin>>greutate >>cost;
for(int i=maxim;i>=0;--i)
if(i+greutate<=g)
sol[i+greutate]=max(sol[i+greutate],cost+sol[i]);
maxim=maxim+greutate;
maxim=min(maxim,g);
--n;
}
fout<<sol[g];
return 0;
}