Pagini recente » Cod sursa (job #3143793) | Cod sursa (job #3270801) | Cod sursa (job #610657) | Cod sursa (job #1286610) | Cod sursa (job #2477194)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
const int DIM = 5007;
const int DIM1 = 1e4+7;
int W[DIM];
int P[DIM];
int dp[DIM][DIM1];
int main()
{
ios::sync_with_stdio(false);
in.tie(0);
int N,G;
in >> N >> G;
for(int i = 1;i <= N;i++)
in >> W[i] >> P[i];
for(int i = 1;i <= N;i++)
for(int cw = 0;cw <= G;cw++)
{
dp[i][cw]=dp[i-1][cw];
if(W[i] <= cw)
dp[i][cw] = max(dp[i][cw],dp[i - 1][cw - W[i]] + P[i]);
}
out << dp[N][G];
return 0;
}