Cod sursa(job #787334)
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 5010
#define MAXG 10010
int n, gmax, pmax;
int g[MAXN],p[MAXN];
int uz[MAXN][MAXG];
int main()
{
freopen("rucsac.in", "r", stdin);
freopen("rucsac.out", "w", stdout);
// Citire
scanf("%d%d", &n, &gmax);
for(int i = 1; i <= n; ++i)
scanf("%d%d", &g[i], &p[i]);
// Dinamica D[i][cw] - profitul maxim pe care-l putem obtine adaugand o submultime a primelor i obiecte, insumand greutatea cw
for(int i = 1; i <= n; ++i)
for(int cw = 0; cw <= gmax; ++cw)
{
// Mai intai nu punem obiectul i.
uz[i][cw] = uz[i-1][cw];
// Daca acest lucru duce la o solutie curenta mai buna, adaugam obiectul i la o solutie anterioara.
if(g[i] <= cw)
uz[i][cw] = max(uz[i][cw], uz[i - 1][cw - g[i]] + p[i]);
}
// Solutia se va afla in statea D[N][G]
pmax = uz[n][gmax];
// Afisare
printf("%d\n", pmax);
return 0;
}