Cod sursa(job #2908097)
Utilizator | Grecu Bogdan grecubogdan | Data | 1 iunie 2022 14:04:58 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.54 kb |
#include <fstream>
#define maxn 5001
#define maxg 10001
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int W[maxn], P[maxn];
int Optim[maxg];
int main()
{
int N, G;
f>>N>>G;
for (int i = 1; i <= N; ++i) {
f>>W[i]>>P[i];
}
Optim[0] = 0;
int sol = 0;
for( int i = 1; i <= N; ++i)
for( int j = G - W[i]; j >= 0; --j) {
if( Optim[j+W[i]] < Optim[j] + P[i] )
{
Optim[j+W[i]] = Optim[j] + P[i];
if( Optim[j+W[i]] > sol)
sol = Optim[j+W[i]];
}
}
g<<sol;
return 0;
}