Cod sursa(job #2493490)
Utilizator | Pescaru Andrei Ateveu | Data | 16 noiembrie 2019 13:05:59 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
short int N, G, W[5005], P[5005],
int DP[5005][10005];
void Read(){
fin>>N>>G;
for(int i = 1; i <= N; i++){
fin>>W[i]>>P[i];
}
}
void Solve(){
for(int i = 1; i <= N; i++)
for(int j = 1; j <= G; j++)
if(j-W[i] >= 0)
DP[i][j] = max(DP[i-1][j],DP[i-1][j-W[i]] + P[i]);
else DP[i][j] = DP[i-1][j];
fout<<DP[N][G];
}
int main()
{
Read();
Solve();
return 0;
}