Cod sursa(job #1853213)
| Utilizator | Data | 21 ianuarie 2017 15:16:00 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 65 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.62 kb |
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,g;
struct obj
{
int pret;
int greutate;
}v[5005];
int d[5005];
int sum_max;
int main()
{
fin>>n>>g;
for (int i=0;i<n;i++) {
fin>>v[i].greutate>>v[i].pret;
}
d[0]=1;
for (int i=0;i<n;i++) {
for (int j=g-v[i].greutate;j>=0;--j) {
if (d[j+v[i].greutate]<d[j]+v[i].pret) {
d[j+v[i].greutate]=d[j]+v[i].pret;
}
}
}
for (int i=0;i<=g;i++) if (d[i]>sum_max) sum_max=d[i];
fout<<sum_max-1;
}
