Cod sursa(job #682666)
| Utilizator | Data | 19 februarie 2012 12:53:57 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.48 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=min(maxim+greutate,g);
--n;
}
int raspuns=0;
for(int i=g;i>=0;--i)
raspuns=max(raspuns,sol[i]);
fout<<raspuns;
return 0;
}