Cod sursa(job #2854507)
Utilizator | FMI Ciltea Marian Marius7122 | Data | 21 februarie 2022 14:26:59 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 25 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.92 kb |
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int N, G, x, y;
vector<int> W, P;
int dp[5001][10001];
ifstream cit("rucsac.in");
ofstream afis("rucsac.out");
int main()
{
cit>>N>>G;
for(int i = 0; i < N; i++){
cit>>x>>y;
W.push_back(x);
P.push_back(y);
}
for(int i = 0; i < N; i++){
for(int j = 0; j <= G; j++){
if(i == 0){
if(j >= W[i]){
dp[i][j] = P[i];
}
else{
dp[i][j] = 0;
}
}
else{
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];
}
}
}
afis<<dp[N-1][G];
cit.close();
afis.close();
return 0;
}