Pagini recente » Cod sursa (job #2489073) | Cod sursa (job #2406880) | Cod sursa (job #1136415) | Cod sursa (job #2724749) | Cod sursa (job #2737743)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
const int maxn = 5005;
const int maxg = 20005;
long long dp[maxg]; /// dp[i][j] = profitul maxim din primele i obiecte cu greutatea j
long long aux[maxn];
int greutate[maxn];
int profit[maxn];
int main()
{
int n, g;
in >> n >> g;
for(int i = 1; i <= n; i++)
in >> greutate[i] >> profit[i];
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= g - greutate[i]; j++)
aux[j + greutate[i]] = max(dp[j + greutate[i]], dp[j] + profit[i]);
for(int j = 0; j < maxg; j++)
dp[j] = aux[j];
}
long long mx = 0;
for(int i = 0; i <= g; i++)
mx = max(mx, dp[i]);
out << mx << "\n";
return 0;
}