Pagini recente » Cod sursa (job #151469) | Istoria paginii utilizator/naomiion | Cod sursa (job #1274853)
#include <fstream>
using namespace std;
ifstream is("rucsac.in");
ofstream os("rucsac.out");
const int MaxN = 5001;
const int MaxG = 10001;
int g[MaxN], v[MaxN];
int n, G;
int lp = 0, lc = 1;
int c[2][MaxG]; // PD 2D
// c[i][j] - val max a obiectelor alese din intervalul [1..i] care nu depasesc
// valoare totala j
void Read();
void Knapsack_2D();
int main()
{
Read();
Knapsack_2D();
os << c[lp][G];
is.close();
os.close();
return 0;
}
void Read()
{
is >> n >> G;
for( int i = 1; i <= n; ++i )
{
is >> g[i];
is >> v[i];
}
}
void Knapsack_2D()
{
for( int i = 1; i <= n; ++i, lc = !lc, lp =! lp )
{
for( int j = 1; j <= G; ++j )
{
c[lc][j] = c[lp][j];
if( j >= g[i] && c[lc][j] < c[lp][j-g[i]] + v[i] )
c[lc][j] = c[lp][j-g[i]] + v[i];
}
}
}