Cod sursa(job #2043476)
| Utilizator | Data | 20 octombrie 2017 09:11:23 | |
|---|---|---|---|
| Problema | Problema rucsacului | Scor | 35 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.68 kb |
#include <bits/stdc++.h>
#define DIM 5001
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n, G;
int C[DIM][2*DIM], gr, c;
void solve()
{
f>>n>>G;
for (int i=1; i<=n; i++)
{
f>>gr>>c;
for (int j=1; j<=G; j++)
if (gr<=j)
if (C[i-1][j]<C[i-1][j-gr]+c)
C[i][j]=C[i-1][j-gr]+c;
else
C[i][j]=C[i-1][j];
else
C[i][j]=C[i-1][j];
}
g<<C[n][G]<<'\n';
f.close();
g.close();
}
int main()
{
solve();
g.close();
return 0;
}
