Pagini recente » Cod sursa (job #2748669) | Cod sursa (job #2491778) | Cod sursa (job #1099935) | Cod sursa (job #892927) | Cod sursa (job #2505802)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int N, G;
int p[5000], g[5000], dp[5000][5000];
int main()
{
fin >> N >> G;
for(int i = 1; i <= N; i++)
{
fin >> g[i] >> p[i];
}
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= G; j++)
{
dp[i][j] = -1;
}
}
//dp[1][g[1]] = p[1];
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= G; j++)
{
if(dp[i-1][j - g[i]] != -1 && j - g[i] >= 0)
{
dp[i][j] = max(dp[i-1][j], dp[i-1][j - g[i]] + p[i]);
}
else
{
dp[i][j] = dp[i-1][j];
}
//fout << dp[i][j] << ' ' ;
}
//fout << '\n';
}
fout << dp[N][G];
return 0;
}