Cod sursa(job #1274853)

Utilizator DreptateeDreptate Alexandru I. Dreptatee Data 24 noiembrie 2014 14:04:28
Problema Problema rucsacului Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#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];
        }
    }

}