Pagini recente » Borderou de evaluare (job #730569) | Cod sursa (job #3195269)
#include <bits/stdc++.h>
using namespace std;
int main()
{
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int n,g;
fin>>n>>g;
vector<vector<int>> dp(n+1,vector<int>(g+1,-1));
vector<pair<int,int>> v(n+1);
for(int i=1; i<=n; i++) fin>>v[i].first>>v[i].second;
dp[0][0] = 0;
for(int i=1; i<=n; i++)
for(int j=0; j<=g; j++)
{
if(j>=v[i].first && dp[i-1][j-v[i].first] != -1)
dp[i][j] = max(dp[i][j],dp[i-1][j-v[i].first]+v[i].second);
dp[i][j] = max(dp[i][j],dp[i-1][j]);
}
int maxi=-1;
for(int i=0; i<=g; i++)
maxi = max(maxi,dp[n][i]);
fout<<maxi;
return 0;
}